János gazda hétvégénként fizikai kísérleteket is végez, és sajnos az egyik próbálkozása balul sikerült: N féregluk keletkezett a legelőjén. A féreglukak a 2D sík különböző pontjaiban jöttek létre, és János számításai szerint N/2 párt alkotnak. Amikor A és B féreglukak párt alkotnak, akkor egy tetszőleges tárgy, ami belép A-ba, B-ből fog kilépni, megtartva eredeti irányát és sebességét. Fordítva is igaz, aki B-be lép be, az A-ban fog kilépni.
Ennek elég kellemetlen következményei lehetnek.
Előfordulhat például, hogy A(1,1) és B(3,1) párt alkotnak, és Riska a tehén a (2,1) pontból indul, +x irányba. Riska belép B(3,1)-be, kilép A(1,1)-ben, aztán megint belép B-be, és így tovább... Riska végtelen ciklusba került!
János ismeri az összes féregluk helyét, és azt is tudja, hogy Riska mindig +x irányban halad, de azt nem tudja, hogy melyik féregluk melyiknek a párja. Ezért szeretné az összes olyan párosítást meghatározni, ahol elő tud fordulni, hogy Riska végtelen ciklusba kerülhet, ha szerencsétlen pontból indul ki.
Feladat
Írjunk programot, ami megadja a veszélyes párosítások számát, ahol Riska végtelen ciklusba kerülhet.
Bemenet
A bemenet első sora a féreglukak N számát adja meg (2 <= N <= 12, páros). Ezután N sorban egy-egy féregluk két koordinátája következik X, Y sorrendben. A koordináták 0 és 1000000000 közé esnek.
Kimenet
Az egyetlen sorba azon párosítások számát kell kiírni, amelyeknél Riska végtelen ciklusba kerülhet.
Példa
| Bemenet |
Kimenet |
4
0 0
1 0
1 1
0 1 | 2
|
Tesztadatok
Címkék
A feladat forrása: USACO training material, Wormholes
Algoritmusok:
megoldás
2004-2016 BDG algoritmus szakkör