Xokkey
Vankuverdə Rusiya xokkey yığmasının uğursuz çıxışından sonra, demək olar ki, hər kəs bu mövzunu müzakirə edir və baş verənlərə dair öz fikirlərini irəli sürürdü. Bəziləri Rusiya yığmasının oyunçularını mübarizə aparmaq istəməməkdə günahlandırır, digərləri isə kanadalıların oyuna olan yüksək motivasiyasına heyran qalırdı. Rusiya xokkey rəhbərləri isə məğlubiyyəti Kanada meydançalarının ölçülərinin Avropa meydançalarından fərqli olması ilə izah etməyə çalışırdılar. Soçidə keçiriləcək növbəti olimpiadada bu məğlubiyyətin əvəzini çıxmaq üçün kanadalıları "rus" meydançaları ilə təəccübləndirmək qərara alındı.
Rusiya xokkey meydançası qabarıq çoxbucaqlı şəklindədir. Belə bir meydançada ruslar kanadalıları və digər rəqibləri mütləq məğlub edəcəklər. Lakin inşaatçılar belə bir meydançanın nişanlanması məsələsi ilə üzləşdilər. İlk növbədə mərkəzi xəttin çəkilməsi qərara alındı. İnşaatçılar qərara gəldilər ki, mərkəzi xətt çoxbucaqlının bəzi iki zirvəsindən keçməli və meydançanı iki "yarımçoxbucaqlı"ya elə bölməlidir ki, kiçik "yarımçoxbucaqlı"nın sahəsinin böyük "yarımçoxbucaqlı"nın sahəsinə nisbəti maksimum dərəcədə 1-ə yaxın və ya 1-ə bərabər olsun.
İnşaatçılara mərkəzi xətti tapmaqda kömək etmək lazımdır.
Giriş verilənləri
Birinci sətirdə tam ədəd T verilir – test bloklarının sayı (1 ≤ T ≤ 10). Sonra T test bloku verilir. Hər bir test bloku çoxbucaqlının zirvələrinin sayı olan N ədədini (4 ≤ N ≤ 2000) və ardınca N sətirdə iki tam ədəd – çoxbucaqlının zirvələrinin koordinatlarını ehtiva edir. Koordinatlar öz mütləq qiymətinə görə 10000-i keçmir.
Çıxış verilənləri
Hər bir test bloku üçün iki sətir çıxış etmək lazımdır. Birinci sətirdə iki ədəd – bölücü diaqonalın keçdiyi zirvələrin nömrələrini yazın. Nömrələr artan qaydada sıralanmalıdır. Nömrələmə 1-dən başlayır və giriş məlumatlarındakı zirvələrin sırasına uyğundur. İkinci sətirdə düzgün qısaldılmamış kəsr – sahələrin nisbətini yazın. Əgər bir neçə düzgün həll mümkündürsə, birinci zirvənin ən kiçik nömrəsi olan həlli çıxış edin. Əgər bu halda da bir neçə düzgün həll mümkündürsə, ikinci zirvənin ən kiçik nömrəsi olan həlli çıxış edin.