Programozás‎ > ‎Feladatok‎ > ‎

Féreglukak

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