G — Irány északnyugat!

Az Irány északnyugat! egy olyan játék, amelyet általában a vidámpark főépületében játszanak, amikor az esetleges esős időjárás eltántorítja a látogatókat a külső látványosságok látogatásától.

A játékot két játékos játssza, és teljes mértékben a szerencsére épül, a játékosoknak alig van befolyásuk a játék kimenetelére.

A játékterv egy nagy térkép a falon, amelyen N különböző város látható. A játék kezdete előtt a játékmester mindkét játékosnak kioszt egy urnát, benne N egyforma golyócskával, amelyek mindegyikében a térképen látható egy-egy város nevével ellátott cetli lapul. Mindkét urna tartalmazza az összes város nevét.

Amikor a játék elkezdődik, az egyik játékos véletlenszerűen kihúz egy golyócskát az urnájából, kinyitja, és megnézi, melyik város szerepel benne. Ezután a másik játékos is húz egy golyócskát véletlenszerűen a saját urnájából, kinyitja, és ő is megnézi a cetlin szereplő városnevet.

Ha a két város ugyanaz, a játék döntetlennel zárul. Ha a városok különbözőek, akkor a játékmester bejelöli a két várost a térképen. Ha az egyik város pontosan északnyugatra fekszik a másiktól, akkor az elsőként húzó játékos nyeri a játékot. Ha az egyik város pontosan északkeletre fekszik a másiktól, akkor a másodikként húzó játékos nyeri a játékot. Minden más esetben a játék döntetlennel zárul. Két város akkor fekszik pontosan északnyugatra vagy északkeletre egymástól, ha a két várost összekötő egyenes és a vízszintes tengely pontosan 45 fokos szöget zár be egymással.

Világosan látható, hogy a játék megnyerésének az esélye nagymértékben függ a városok elhelyezkedésétől a térképen. A városok koordinátáit előre ismerjük. A feladatod, hogy meghatározd annak a valószínűségét, hogy valaki megnyeri a játékot.

A bemenet specifikációja

A bemenet számos tesztesetet tartalmaz. Minden teszteset egy olyan sorral kezdődik, amely egyetlen N egész számból, a térképen található városok számából áll (1 ≤ N ≤ 10⁵). Ezt N sor követi, amelyek mindegyike két, egymástól egy szóközzel elválasztott egész számot tartalmaz, valamelyik város két koordinátáját. A koordináták hagyományos síkbeli, Descartes-féle koordináták. Egyik koordináta abszolút értéke sem haladja meg a 10⁹-t.

A kimenet specifikációja

Minden tesztesetre egyetlen sort kell a kimenetre írni, amely egy P valós számot tartalmaz: annak a valószínűségét, hogy valamelyik játékos megnyeri a játékot. P-t 10^–6 megengedett legnagyobb hibával kell kiírni.

Példa bemenet

1. 4
2. 1 2
3. 2 1
4. 1 1
5. 2 2
6. 3
7. 3 1
8. 2 2
9. 1 3

letöltés szöveges állományként

A példa bemenethez tartozó kimenet

1. 0.25
2. 0.666667

letöltés szöveges állományként

Eredeti feladat

Czech Technical University Open Contest 2017