Clustering
Есенен Турнир по Информатика 2011
Time Limit: 1s, Memory Limit: 64MiB
Ако помните задачата Sheep трябва да знаете, че Ели често сънува как разхожда стадото си с овце. А пашата на нейните животни (както в миналата задача, така и в тази) не е лесно начинание. Ели, също така, има и кучета, които охраняват стадото ѝ от вълци и крадци. Опасността за всяка овца се определя от разстоянието ѝ до най-близкото куче. Опасността за цялото стадо пък е сумата от опасностите за всяка овца.

Ако считаме поляните за сравнително полегати (а това в общия случай е така, тъй като стадото ѝ не си пада особено по катеренето), можем да представим овцете като N точки в двумерно Евклидово пространство. Ели се чуди как да разположи своите кучета-пазачи (К точки в същото пространство), така че опасността за стадото да е минимална.

Казано с други думи, дадени са ви N точки чрез своите координати (Xi, Yi). От вас се иска да поставите нови K точки така, че сумата от минимумите на разстоянията от всяка от дадените точки до някоя от сложените от вас е възможно най-малка.
Вход
На първия ред на стандартния вход са зададени целите числа N и K. Всеки от следващите N реда съдържа по две цели числа Xi и Yi – съответно координатите на i-тата овца.
Изход
На стандартния изход изведете К на брой двойки реални числа – координатите на кучетата-пазачи. Разрешено е те да съвпадат с координатите на някои от овцете.
Ограничения
  • 1 ≤ K < N ≤ 1,000
  • 1 ≤ K ≤ 100
  • 0 ≤ Xi, Yi ≤ 10,000
Оценяване
За всеки тест вашето решение ще получи min(1, (author_score / your_score))3 от максималните точки за всеки тест, където author_score е резултатът, намерен от авторското решение, your_score е резултатът, намерен от вашето решение.
Примерен Вход Примерен Изход
7 2 1 2 1 4 2 5 3 2 4 4 5 6 6 5 1.750000 3.250000 5.000000 5.000000
Забележете, че можете да изведете неоптимално решение.
Мрън!