Розподіл Землі#1278
Король Королівства Далеко-далеко помер, і королівство необхідно поділити між його синами. Королівство, яке можна зобразити у вигляді прямокутної карти, складається з міст. Щоб поділити землю, на карті буде проведено K-1 прямих відрізків, кожен з яких паралельний або вертикальній, або горизонтальній осі. Це розділяє карту на рівно прямокутників, усі з яких мають однакову висоту (якщо відрізки вертикальні) або однакову ширину (якщо відрізки горизонтальні). Жоден відрізок не повинен перетинати жодного з міст. Далі кожному сину випадковим чином буде призначена одна з областей, і міста, що потрапили до цієї області, стануть його часткою.
Звісно, вони хочуть, аби поділ був якомога справедливішим: теоретично, у найсправедливішому поділі кожен син має отримати по міст (ми назвемо це значення базовим числом), але оскільки базове число не завжди є цілим, кожен із синів хоче, щоб його частка була якомога ближчою до базового числа. Несправедливість для кожного сина обчислюється як абсолютна різниця між кількістю міст, що дісталися йому, та базовим числом. Найсправедливішим є такий поділ, що мінімізує середню несправедливість для всіх синів.
Розглянемо приклад вище з синами та містами (тобто базове число — 6/3 = 2.0). На малюнку (a) зображено початкову карту. На малюнку (b) показано не найоптимальніший поділ (пунктирні лінії — це лінії поділу). У такому разі центральна область містить міста (несправедливість |3-2| = 1), ліва область містить місто (несправедливість |1-2| = 1), а права область містить міста (ідеально справедливо, несправедливість ), тому середня несправедливість становить .
На малюнку (c) справа зображено оптимальний поділ, оскільки всі три області містять однакову кількість міст, і середня несправедливість дорівнює .
Напишіть програму, що визначає найбільш справедливий поділ земель для заданого королівства.
Ваша програма буде протестована на одному або декількох тестових випадках. Кожен тест описується на N+1 рядках.
У першому рядку кожного тесту задано два додатних цілих числа: N \leq 100\,000 та K \leq 10, де — кількість міст, а — кількість дітей. Зауважте, що K \leq N.
Далі подано рядків, у кожному з яких вказано координати міста — два числа , де 0 \leq x, y \leq 100\,000. Оскільки координати округлено до цілих чисел, кілька міст можуть мати однакові координати на карті. Ви можете вважати, що карта королівства — це будь-який прямокутник, що містить усі задані точки (хоча ця інформація програмі не потрібна). Також зверніть увагу, що хоча всі міста лежать на цілих координатах, лінії поділу не обов'язково мають проходити по цілих координатах.
Останній рядок у файлі містить два нулі.
Для кожного тесту виведіть наступний рядок:
k. A/B
де — номер тесту (починаючи з ), а — мінімальне середнє значення несправедливості, якого можна досягти. має бути нескоротним дробом. Нехай B=1, якщо результат ціле число.
Примітка: Перед стоїть пробіл.
Приклад 1