Problem 1260: triunghi

În comuna Triunghi din România sunt $n$ ţărani codificaţi prin numerele $1, 2, \ldots , 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.care sunt înconjurate de uscat doar prin interiorul terenului nu şi prin afara acestuia.

Cerință

Să se scrie un program care să determine:

Codurile ţăranilor care au documente cu suprafeţe de pământ ce conţin în interior sau pe frontieră fântâna
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: $x_1$ , $y_1$ , $x_2$ , $y_2$ , $x_3$ , $y_3$ , ce reprezintă coordonatele celor trei colţuri ale suprafeţei triunghiulare deţinute de un ţăran. ( $x_1, x_2, x_3$ abscise, iar $y_1, y_2, y_3$ ordonate).

Pe linia $i+1$ se află coordonatele colţurilor suprafeţei de teren triunghiulare deţinute de ţăranul i, $i = 1,2, \ldots , 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 $1$ , 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 $2$ , adică: codul ţăranului cu proprietatea cerută, sau cifra $0$ , dacă nu există un astfel de ţăran.

Restricții și precizări

$2 \leq n \leq 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

Exemplu

triunghi.in

3
10 0 0 10 10 10
0 100 100 0 -100 0
0 0 10 0 0 10
10 5

triunghi.out

2 1 2
2

Explicație

La punctul $1$ , 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 $2$ , ţă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$ ).

triunghi