Torpaq Bölməsi#1278
Uzaq, Uzaq Diyarın kralı vəfat edib və krallıq onun oğulları arasında bölüşdürülməlidir. Düzbucaqlı xəritə ilə göstərilə bilən bu krallıq şəhərdən ibarətdir. Torpağı bölmək üçün xəritədə K-1 düz xətt çəkiləcək, bunların hər biri ya şaquli, ya da üfüqi oxlara paralel olacaq. Bu, xəritəni dəqiq düzbucaq bölgəyə ayırır, bu bölgələrin ya hamısının hündürlüyü (bölən xətlər şaqulidirsə), ya da hamısının eni (əgər bölən xətlər üfüqidirsə) bərabər olacaq. Heç bir xətt şəhərin üzərindən keçə bilməz. Sonra isə hər oğula təsadüfi olaraq bir bölgə veriləcək və həmin bölgədəki şəhərlər onun payı olacaq.
Təbii ki, onlar bu bölgünü mümkün qədər ədalətli etmək istəyirlər: nəzəri baxımdan ən ədalətli bölümdə hər oğul şəhər almalıdır (bu ədəd "bazis" adlanacaq), lakin bazis həmişə tam ədəd olmadığından, hər oğul bu ədəddən mümkün qədər az fərqlə pay almaq istəyir. Hər bir oğul üçün ədalətsizlik payına düşən şəhər sayı ilə bazis arasındakı modullu fərqlə hesablanır. Ən ədalətli bölgü, bütün oğullar üçün orta ədalətsizliyin minimum olduğu bölgüdür.
Yuxarıdakı nümunəni nəzərdən keçirək: oğul və şəhər var (bazis 6/3 = 2.0). (a) hissədə xəritənin orijinal hali göstərilib. (b) hissədə qeyri-optimal bir bölgü (kəsik xətlər bölücü xəttdir). Bu halda, orta bölgədə şəhər var (|3-2|=1 ədalətsizlik), sol bölgədə şəhər (|1-2|=1 ədalətsizlik), sağ bölgədə isə şəhər (tam ədalətli, ədalətsizlik), belə ki, orta ədalətsizlik olur.
(c) hissədə isə optimal bölgü göstərilib, çünki bütün üç bölgədə bərabər şəhər sayı var və orta ədalətsizlik -dır.
Verilmiş krallıq üçün ən ədalətli bölgünün tapılması üçün proqram yazın.
Proqramınız bir və ya bir neçə test tapşırığından yoxlanılacaq. Hər test tapşırığı N+1 sətirdə təsvir olunur.
Hər test tapşırığının ilk sətrində iki müsbət tam ədəd verilir: N \leq 100\,000 və K \leq 10, burada şəhərlərin sayı, isə uşaqların sayıdır. Qeyd: K \leq N.
Sonra sətrin hər birində xəritədə bir şəhərin koordinatları verilir – iki tam ədəd , burada 0 \leq x, y \leq 100\,000. Koordinatlar tam ədədə yuvarlaqlandığı üçün, bir neçə şəhər eyni koordinatlarda ola bilər. Xəritənin istənilən bütün bu nöqtələri daxil edən düzbucaqlı kimi təyin olunduğunu qəbul edə bilərsiniz (lakin proqram üçün bu məlumat lazım deyil). Qeyd: bütün şəhərlər tam ədəd koordinatındadır, lakin bölgü xətləri məcbur deyil ki, tam ədəd koordinatdan keçsin.
Giriş faylının son sətrində iki sıfır verilir.
Hər test tapşırığı üçün aşağıdakı formada sətir çap edin:
k. A/B
Burada test tapşırığının nömrəsi (1-dən başlayaraq), isə əldə edilə bilən minimal orta ədalətsizliyin sadə kəsr şəklində dəyəridir. qeyri-azaldılmış kəsr olmalıdır. Əgər nəticə tam ədədə bərabərdirsə, B=1 götürülür.
Qeyd: -dan əvvəl bir boşluq qoyulmalıdır.
Nümunə 1