Alice və Bomb
Alice və Bob bir vaxtlar bir-birinə aşiq idilər, amma indi bir-birlərindən nifrət edirlər.
Bir gün, Alice bir çanta tapdı. Bu çanta Bobun görüşə gedərkən istifadə etdiyi çantaya bənzəyirdi. Birdən Alice tık-tak səsi eşitdi. Alice intuisiyası ilə düşündü ki, Bob onu bomba ilə öldürmək istəyir. Xoşbəxtlikdən, bomba hələ partlamamışdı və binaların arxasında gizlənmək üçün bir az vaxtı vardı.
ACM şəhərinin görünüşü sonsuz bir müstəvi kimi təsvir edilə bilər və hər bina bir çoxbucağı təşkil edir. Alice bir nöqtə kimi qəbul edilir və bomba partlayışı Alice-ə çata bilər, əgər Alice və bomba arasında olan xətt parçası hər hansı bir binanın daxili mövqeyini kəsmirsə. Bomba partlayışının sürətinin sonsuz olduğunu fərz edin; bomba partladıqda, onun partlayış dalğası hər yerə dərhal çatacaq, əgər bomba partlayışı bəzi binalar tərəfindən kəsilməzsə.
Aşağıdakı şəkil bomba partlayışının nümunəsini göstərir. Sol şəkil bombanı və binaları (qara ilə doldurulmuş çoxbucaqlar) göstərir. Sağ şəkil isə bomba partlayışından sonra partlayış dalğasının təsiri altında olan sahəni (boz rənglə rənglənmiş) göstərir.
Şəkil 1: Bomba partlayışının nümunəsi
Qeyd edək ki, Alice və bombanı birləşdirən xətt parçası bir binanın sərhədinə toxunsa belə, bomba partlayışı hələ də Alice-i vurub apara bilər. Alice erkən qaçmaq istədiyi üçün, özünü bina ilə gizlətmək üçün qaçdığı məsafəni minimuma endirmək istəyir.
Sizin vəzifəniz Alice, bomba və binaların mövqelərini oxuyan və Alice-in bina arxasında gizlənməsi üçün qaçması lazım olan minimum məsafəni hesablayan bir proqram yazmaqdır.
Giriş verilənləri
Giriş bir neçə test halını ehtiva edir. Hər test halı aşağıdakı formata malikdir:
N bx by m_1 x_{1,1} y_{1,1} ... x_{1,m1} y_{1,m1} ... m_N x_{N,1} y_{N,1} ... x_{N,mN} y_{N,mN}
Hər test halının ilk sətri N (1 ≤ N ≤ 100) tam ədədini ehtiva edir, bu da binaların sayını göstərir. İkinci sətirdə iki tam ədəd bx və by (−10000 ≤ bx, by ≤ 10000) var, bu da bombanın yerini göstərir. Sonra, N sətir gəlir, binaların məlumatlarını göstərir.
Binanın məlumatı nöqtələrdən ibarət bir çoxbucaq kimi verilir. Hər sətir üçün, çoxbucağın neçə nöqtəsi olduğunu göstərən bir tam ədəd m_i (3 ≤ m_i ≤ 100, m_i ≤ 500) var və sonra nöqtənin x və y koordinatlarını təmin edən m_i cüt tam ədəd x_{i,j}, y_{i,j} gəlir.
Aşağıdakıları fərz edə bilərsiniz:
çoxbucaq öz-özünə kəsişmələrə malik deyil.
hər hansı iki çoxbucaq ümumi nöqtəyə malik deyil.
nöqtələr dəsti saat əqrəbi istiqamətinin əksinə sıradadır.
Alice və bombanın ilkin mövqeləri çoxbucağın içində yerləşməyəcək.
verilmiş çoxbucağın seqmentinin uzadılmış xətləri üzərində bomba yoxdur.
Alice ilkin olaraq (0, 0) nöqtəsində yerləşir. Mümkündür ki, Alice çoxbucağın sərhədində yerləşsin.
N = 0 girişin sonunu göstərir. Bunu test halı kimi işləməməlisiniz.
Çıxış verilənləri
Hər test halı üçün, Alice-in bina arxasında gizlənməsi üçün qaçması lazım olan minimum məsafəni ehtiva edən bir sətir çıxarın. Cavabınızdakı mütləq səhv və ya nisbi səhv 10^{−6}-dan az olmalıdır.