În comuna Triunghi din România sunt n ţărani codificaţi prin numerele 1, 2, ..., n. După anul 1990 a început retrocedarea suprafeţelor de pământ deţinute înainte de colectivizare. Fiecare ţăran are un document prin care dovedeşte că este proprietar pe o singură suprafaţă de teren de formă triunghiulară. Din păcate, documentele dau bătaie de cap primarului (care se ocupă de retrocedarea suprafeţelor de pământ), pentru că sunt porţiuni din suprafeţele de pământ care se regăsesc pe mai multe documente.
În această comună există o fântână cu apă, fiind posibil ca ea să fie revendicată de mai mulţi ţărani. O suprafaţă de pământ este dată prin coordonatele celor trei colţuri, iar fântâna este considerată punctiformă şi dată prin coordonatele punctului.

Cerinţă

Să se scrie un program care să determine:
a) Codurile ţăranilor care au documente cu suprafeţe de pământ ce conţin în interior sau pe frontieră fântâna.
b) Codul ţăranului ce deţine un document cu suprafaţa de teren, care include toate celelalte suprafeţe.

Date de intrare

Fişierul de intrare triunghi.in are pe prima linie numărul n de ţărani, pe următoarele n linii câte 6 valori numere întregi separate prin câte un spaţiu, în formatul: x1 y1 x2 y2 x3 y3, ce reprezintă coordonatele celor trei colţuri ale suprafeţei triunghiulare deţinute de un ţăran. (x1, x2, x3 abscise, iar y1, y2, y3 ordonate). Pe linia i+1 se află coordonatele colţurilor suprafeţei de teren triunghiulare deţinute de ţăranul i, i=1,2,…,n. Ultima linie a fişierului (linia n+2) va conţine coordonatele fântânii în formatul x y, cu un spaţiu între ele (x abscisă, iar y ordonată).

Date de ieşire

Fişierul de ieşire triunghi.out va conţine pe prima linie răspunsul de la punctul a), adică: numărul de ţărani care îndeplinesc condiţia din cerinţă şi apoi codurile lor (în ordine crescătoare), cu un spaţiu între ele. Dacă nu există ţărani cu condiţia din cerinţă, pe prima linie se va scrie cifra 0. Pe linia a doua se va scrie răspunsul de la punctul b), adică: codul ţăranului cu proprietatea cerută, sau cifra 0, dacă nu există un astfel de ţăran.

Restricţii

• 2 ≤ n ≤ 65
• coordonatele colţurilor suprafeţelor de pământ şi ale fântânii sunt numere întregi din intervalul [-3000, 3000]
• cele trei colţuri ale fiecărei suprafeţe de pământ sunt distincte şi necoliniare
• nu există doi ţărani care să deţină aceeaşi suprafaţă de pământ
• nu se acordă punctaje parţiale.

Exemple

triunghi.in	triunghi.out	Explicaţii
3 10 0 0 10 10 10 0 100 100 0 -100 0 0 0 10 0 0 10 10 5	2 1 2 2	La punctul a), sunt doi ţărani care deţin suprafeţe de pământ ce au în interior sau pe frontieră fântâna, cu codurile 1 şi 2. La punctul b), ţăranul cu codul 2 deţine o suprafaţă de teren care include, suprafeţele de pământ deţinute de ceilalţi ţărani (cu codurile 1 şi 3).

autor: Prof. Doru Popescu Anastasiu

propunător: Prof. Marinel Şerban

Liceul de Informatică “Grigore Moisil”

marinel_serban@yahoo.com