NézetNyomtat

Pontok
Címkék > Feladat

Pontok

Adott a síkon egy ponthalmaz. Azt mondjuk, hogy egyenesek egy halmaza lefedi a ponthalmazt, ha a ponthalmaz bármely pontja rajta van valamelyik egyenesen.

Feladat

Írj olyan programot, amely eldönti, hogy adott ponthalmaz lefedhető-e legfeljebb három egyenessel! A program adjon is meg három ilyen egyenest, ha van lefedés.

Bemenet

A PONTOK.BE szöveges állomány első sorában a pontok N (1$\le$N$\le$10000) száma van. A következő N sor mindegyikében két egész szám van egy szóközzel elválasztva: x y, egy pont x-koordinátája és y-koordinátája (-20000$\le$x,y$\le$20000).

Kimenet

A PONTOK.KI szöveges állomány első sorába négy 0 számot kell írni (egy-egy szóközzel elválasztva) ha a ponthalmaz nem fedhető le három egyenessel. Egyébként az állományba három sort kell írni, mindhárom sorba egy-egy lefedő egyenest megadó négy egész számot kell írni: x1; y1; x2; y2, ami az (x1, y1), és (x2, y2) pontokon átmenő egyenest jelenti. Ha a ponthalmaz lefedhető háromnál kevesebb egyenessel, akkor is három sort (egyenest) kell kiírni; a felesleges egyenesek tetszőlegesek.

Példa

pontok.bepontok.ki
8
2 3
4 2
6 4
2 5
8 5
6 6
4 7
2 8
2 3 2 8
2 8 8 5
4 2 6 4

Tesztadatok