Torpaq Bölməsi
Uzaq, Uzaq Krallığın kralı vəfat edib və krallıq onun K oğulları arasında bölünməlidir. Düzbucaqlı xəritədə yerləşən krallıq N şəhərdən ibarətdir. Torpağı bölmək üçün xəritədə K-1 düz xətt seqmentləri çəkiləcək, bunlar ya xəritənin şaquli, ya da üfüqi oxuna paralel olacaq. Bu, xəritəni dəqiq K bərabər hündürlükdə (əgər bölmə xətləri şaquli olarsa) və ya bərabər enlikdə (əgər bölmə xətləri üfüqi olarsa) düzbucaqlara bölür. Heç bir seqment şəhərlərdən keçməməlidir. Hər oğula təsadüfi olaraq K bölgədən biri təyin ediləcək və həmin bölgədəki şəhərlər onun payı olacaq.
Əlbəttə, onlar bölünmənin mümkün qədər ədalətli olmasını istəyirlər: nəzəri olaraq, ən ədalətli bölünmədə hər oğul N/K şəhər almalıdır (bu dəyəri əsas xətt adlandıracağıq), lakin əsas xətt həmişə tam ədəd olmadığından, hər oğul mümkün qədər əsas xəttə yaxın olmaq istəyir. Hər oğulun ədalətsizliyi ona təyin edilən şəhərlərin sayı ilə əsas xətt arasındakı mütləq fərq kimi hesablanacaq. Ən ədalətli bölünmə, bütün oğulların orta ədalətsizliyini minimuma endirən bölünmədir.
Yuxarıdakı nümunəni nəzərdən keçirin: 3 oğul və 6 şəhər (beləliklə, əsas xətt 6/3 = 2.0) Şəkil (a) orijinal xəritədir. Şəkil (b) optimal olmayan bölünməni göstərir (kəsik xətlər 2 bölmə xəttidir.) Bu halda, orta bölgə 3 şəhərdən ibarətdir (ədalətsizlik |3 - 2| = 1), sol bölgə 1 şəhərdən ibarətdir (ədalətsizlik |1 - 2| = 1), sağ bölgə isə 2 şəhərdən ibarətdir (tamamilə ədalətli, ədalətsizlik 0), beləliklə, orta ədalətsizlik 2/3 olur.
Sağdakı Şəkil (c) optimal bölünməni göstərir, çünki hər üç bölgə eyni sayda şəhərdən ibarətdir və orta ədalətsizlik 0 olur.
Verilmiş krallıq üçün ən ədalətli torpaq bölünməsini müəyyən edən bir proqram yazın.
Giriş verilənləri
Proqramınız bir və ya daha çox test halında sınaqdan keçiriləcək. Hər test halı N+1 sətirdə təsvir edilir.
Hər test halının ilk sətri iki müsbət tam ədədi göstərir: (N ≤ 100, 000) və (K ≤ 10) burada N şəhərlərin sayı və K uşaqların sayıdır. Qeyd edək ki, K ≤ N.
Sonra N sətir gəlir, hər biri bir şəhərin koordinatlarını iki tam ədəd (x, y) ilə təsvir edir, burada 0 ≤ x, y ≤ 100, 000. Koordinatlar ən yaxın tam ədədə yuvarlaqlaşdırıldığından, xəritədə eyni koordinata malik bir neçə şəhər ola bilər. Krallığın xəritəsinin verilmiş bütün nöqtələri əhatə edən hər hansı bir düzbucaq olduğunu qəbul edə bilərsiniz (baxmayaraq ki, belə bir məlumat proqram tərəfindən tələb olunmur.) Qeyd edək ki, bütün şəhərlər tam ədədi koordinatlarda yerləşsə də, bölmə xətləri buna ehtiyac duymur.
Giriş faylının son sətri iki sıfırdan ibarətdir.
Çıxış verilənləri
Hər test halı üçün aşağıdakı sətri çap edin:
k. A/B
Burada k test halının nömrəsidir (birincidən başlayaraq) və A/B əldə edilə bilən minimum orta ədalətsizlikdir. A/B sadələşdirilmiş kəsr olmalıdır. Nəticə tam ədəd olduqda B=1 olsun.
Qeyd: A əvvəlində boşluq var.