{"code":"thttinhbc6","name":"Siêu thị (THT BC Vòng Tỉnh/TP 2022)","description":"###Siêu thị (Bài 3 bảng C1)\r\n\r\nCó $n$ khu vực dân cư, khu vực $i$ ở vị trí ($x_i, y_i$). Người ta muốn đặt $k$ siêu thị để cung cấp hàng hóa cho $n$ khu vực dân cư này. Người dân ở khu vực dân cư $i$ khi mua hàng sẽ chọn siêu thị gần nhất, do đó tiêu chí đánh giá việc đặt $k$ siêu thị dựa trên giá trị: tổng các khoảng cách của từng khu vực dân cư đến siêu thị gần nhất, giá trị này càng nhỏ càng thể hiện việc chọn là tối ưu.\r\n\r\n**Yêu cầu**: Cho $n, k$ và tọa độ của $n$ khu dân cư. Hãy xác định vị trí đặt $k$ siêu thị để tổng các khoảng cách của từng khu vực dân cư đến siêu thị gần nhất càng nhỏ càng tốt.\r\n\r\n####Input \r\n- Dòng đầu chứa hai số nguyên $n,k\\ (k \\le n)$;\r\n- $n$ dòng sau, mồi dòng chứa hai số thực $x_i,y_i$ ($0 \\le x_i,y_i \\le 10000$).\r\n\r\n####Output\r\n- Ghi ra gồm $k$ dòng, mỗi dòng chứa 2 số thực là tọa độ của các siêu thị\r\n\r\n**Cách tính điểm**: Với mỗi test điểm số tính theo công thức dưới đây: $min\\left( 1,\\left( \\frac{\\text{tổng khoảng cách theo phương án của giám khảo}}{\\text{tổng khoảng cách theo theo phương án của thí sinh}} \\right) \\right)^2$\r\n\r\n####Scoring\r\n- \tSubtask $1$ ($50\\%$ số điểm): $n \\le 15$;\r\n- \tSubtask $2$ ($50\\%$ số điểm): $n \\le 1000$.\r\n\r\n####Example\r\n!!! question \"Test 1\"\r\n    ???+ \"Input\"\r\n        ```sample\r\n        5 2\r\n        0 0\r\n        1 0\r\n        1 1\r\n        0 1\r\n        9 9 \r\n        ```\r\n    ???+ success \"Output\"\r\n        ```sample\r\n        0.5 0.5\r\n        9 9\r\n        ```","points":200.0,"partial":false,"time_limit":1.0,"memory_limit":262144,"short_circuit":false,"allowed_languages":[3,4,34,36,37,5,6,11,12,14,28,2,38,39,9,18,17,29,23,27,35,25,26,10,7,19,32,1,8,15,16,24,20,33,13,41,21,40],"is_public":true,"is_manually_managed":false,"permissions":{"can_edit":false}}