Programozás‎ > ‎Feladatok‎ > ‎

Poligon

Adott a síkon egy N csúcspontot tartalmazó zárt, nem metsző törtvonal a csúcsok felsorolásával. Tehát a felsorolásban az i-edik és i+1-edik (i<N) pont van összekötve egyenes szakasszal, illetve az N-edik az elsővel.  

Feladat

Készíts programot, amely megadja azokat az A,B csúcspárokat, amelyekre teljesül, hogy a törtvonal minden A-tól és B-től különböző pontja szigorúan balra van, ha A-ból B-felé nézünk!

Bemenet

A poligon.be szöveges állomány első sorában a csúcspontok N száma (3≤N≤10 000) van. A következő N sor mindegyike két X Y 
(-1 000 000≤X, Y≤1 000 000) egész számot tartalmaz, egy csúcspont x- és y-koordinátáját. 

Kimenet

A poligon.ki szöveges állomány első sorába azon csúcspárok M számát kell írni, amelyekre teljesül a kívánt feltétel. A következő M sor mindegyike egy megfelelő csúcspár A és B sorszámát tartalmazza, egy szóközzel elválasztva. A csúcspárokat tetszőleges sorrendben ki lehet írni. A pontpár A és B sorrendje lényeges! 

Példa

Bemenet  Kimenet
11
6 6
10 6
7 4
12 4
10 8
6 7
7 10
8 9
8 13
3 4
5 2		4
10 11
11 4
4 9
9 10


Tesztadatok

Címkék

A feladat forrása: NTOITV 2013, 11-13. évfolyam, döntő
Algoritmusok: konvex burok