{"code":"22thtbc6","name":"Siêu thị","description":"Có $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 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\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\r\n - Gồm $k$ dòng, mỗi dòng chứa hai số thực là tọa độ của các siêu thị.\r\n\r\n#### Scoring \r\n\r\n - Subtask $1$ ($50\\%$ số điểm): $n \\le 15$.\r\n - Subtask $2$ ($50\\%$ số điểm): $n \\le 5000$.\r\n - Cách tính điểm: Với mỗi test, gọi tổng khoảng cách theo phương án của giám khảo là $res$, gọi tổng khoảng cách theo phương án của thí sinh là $ans$, điểm số tính theo công thức sau: $min(1,(\\frac{res}{ans}))^2$.\r\n\r\n#### Example\r\n\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        \r\n    ???+ success \"Output\"\r\n        ```sample\r\n        0.5 0.5\r\n        9 9\r\n        ```","points":2600.0,"partial":true,"time_limit":1.0,"memory_limit":1048576,"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}}