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
|