== include(page="template/taskheader" task_id="triunghi2") ==
Poveste si cerinta...
In comuna Triunghi din Romania sunt $n$ tarani codificati prin numerele {$1$}, {$2$}, ..., {$n$}. Dupa anul 1990 a Inceput retrocedarea suprafetelor de pamant detinute inainte de colectivizare. Fiecare taran are un document prin care dovedeste ca este proprietar pe o singura suprafata de teren de forma triunghiulara. Din pacate, documentele dau bataie de cap primarului (care se ocupa de retrocedarea suprafetelor de pamant), pentru ca sunt portiuni din suprafetele de pamant care se regasesc pe mai multe documente.
In aceasta comuna exista o fantana cu apa, fiind posibil ca ea sa fie revendicata de mai multi tarani. O suprafata de pamant este data prin coordonatele celor trei colturi, iar fantana este considerata punctiforma si data prin coordonatele punctului.
h2. Cerinta
Sa se scrie un program care sa determine:
# Codurile taranilor care au documente cu suprafete de pamant ce contin in interior sau pe frontiera fantana.
# Codul taranului ce detine un document cu suprafata de teren, care include toate celelalte suprafete.
h2. Date de intrare
...
Fisierul de intrare $triunghi2.in$ are pe prima linie numarul $n$ de tarani, pe urmatoarele $n$ linii cate $6$ valori numere intregi separate prin cate un spatiu, in formatul: {$x{~1~} y{~1~} x{~2~} y{~2~} x{~3~} y{~3~}$}, ce reprezinta coordonatele celor trei colturi ale suprafetei triunghiulare detinute de un taran. ({$x{~1~} x{~2~} x{~3~}$} abscise, iar {$y{~1~} y{~2~} y{~3~}$} ordonate). Pe linia $i+1$ se afla coordonatele colturilor suprafetei de teren triunghiulare detinute de taranul {$i$}, {$i=1,2,...,n$}. Ultima linie a fisierului (linia {$n+2$}) va contine coordonatele fantanii in formatul {$x y$}, cu un spatiu intre ele ({$x$} abscisa, iar {$y$} ordonata).
h2. Date de iesire
...
Fisierul de iesire $triunghi2.out$ va contine pe prima linie raspunsul de la punctul 1), adica: numarul de tarani care indeplinesc conditia din cerinta si apoi codurile lor (in ordine crescatoare), cu un spatiu intre ele. Daca nu exista tarani cu conditia din cerinta, pe prima linie se va scrie cifra {$0$}. Pe linia a doua se va scrie raspunsul de la punctul 2), adica: codul taranului cu proprietatea ceruta, sau cifra {$0$}, daca nu exista un astfel de taran.
h2. Restrictii
* $... ≤ ... ≤ ...$
* $2 ≤ n ≤ 65$
* coordonatele colturilor suprafetelor de pamant si ale fantanii sunt numere intregi din intervalul [{$-3000, 3000$}]
* cele trei colturi ale fiecarei suprafete de pamant sunt distincte si necoliniare
* nu exista doi tarani care sa detina aceeasi suprafata de pamant
* nu se acorda punctaje partiale.
h2. Exemplu
table(example). |_. triunghi2.in |_. triunghi2.out |
| This is some
text written on
multiple lines.
| This is another
text written on
multiple lines.
| 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
|
h3. Explicatie
...
La punctul 1), sunt doi tarani care detin suprafete de pamant ce au in interior sau pe frontiera fantana, cu codurile $1$ si {$2$}.
La punctul 2), taranul cu codul $2$ detine o suprafata de teren care include, suprafetele de pamant detinute de ceilalti tarani (cu codurile $1$ si {$3$}).
== include(page="template/taskfooter" task_id="triunghi2") ==
== SmfTopic(topic_id="...") ==
