Pul kisəsi ya da həyatınız
Conni və dostları Halloween gecəsini kəndlərindəki evlərdən konfet toplamaqla keçirməyə qərar verdilər. Kənd çox böyük olduğundan və bütün evlərdən konfet toplamaq üçün bir qrup kifayət etmədiyindən, Conni və dostları bölünməyə qərar verdilər ki, hər biri fərqli evlərə getsin, orada konfet toplasın (və ya əgər sakinlər konfet verməsələr, qarışıqlıq salsın) və əvvəlcədən razılaşdırılmış görüş yerinə qayıtsın.
Kənddə n ev var, onların mövqeləri evklid müstəvisindəki dekart koordinatları ilə müəyyən edilə bilər. Conni'nin də daxil olduğu dostlar qrupu da n nəfərdən ibarətdir. Onlar bütün qənimətlərlə qayıtdıqdan sonra konfetləri bölüşdürməyə qərar verdilər. Evlər uzaqda ola bilər, lakin Conni konfetləri mümkün qədər tez yemək istəyir.
Bəzi kənd sakinlərinin qonaqpərvərliyinə görə yerli hakimiyyət orqanlarının bəzi uşaqları axtara biləcəyini nəzərə alaraq, onlar görüş yerini kənddən keçən çayın yanında, y = 0 xətti üzərində təyin etməyə qərar verdilər. Qeyd edək ki, çayın hər iki tərəfində evlər ola bilər və bəzi evlər üzən evlər ola bilər (y = 0). Hər bir uşağın gediş sürəti 1 metr/saniyədir və onlar müstəvidə istənilən istiqamətdə hərəkət edə bilərlər.
Tam gecə yarısı hər bir uşaq seçdiyi evin qapısını döyəcək, dərhal konfetləri götürəcək və görüş yerinə ən qısa marşrutla qayıdacaq. Conni'ye konfetləri yeməyə nə vaxt başlaya biləcəyini bildirin.
Giriş verilənləri
Hər bir test n evlərin sayını ehtiva edən bir sətirlə başlayır (1 ≤ n ≤ 50000). Növbəti n sətir evlərin mövqelərini təsvir edir. Hər bir sətir iki həqiqi ədəd x və y (-200 000 ≤ x, y ≤ 200 000) ehtiva edir - evin metrlə koordinatları. Bütün evlər fərqli yerlərdədir. Hər bir testdən sonra boş bir sətir yerləşir. n = 0 olan sətir giriş məlumatlarının sonunu göstərir və işlənmir.
Çıxış verilənləri
Hər bir test üçün bir sətirdə iki ədəd çıxarın: y = 0 xəttində görüş nöqtəsinin x koordinatı, sonuncu uşağın çatma vaxtını minimallaşdıran və bu vaxtın özü (gecə yarısından sonra saniyələrlə ölçülür). Rəqəmləri 4 onluq rəqəmlə çıxarın.