| Fişierul intrare/ieşire: | triunghi2.in, triunghi2.out | Sursă | ONI 2007, clasa 9 |
| Autor | Doru Popescu Anastasiu | Adăugată de |  Adrian Diaconu •DITzoneC |
| Timp execuţie pe test | 0.1 sec | Limită de memorie | 20480 kbytes |
| Scorul tău | N/A | Dificultate | N/A |
Vezi solutiile trimise | Statistici
Triunghi2
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.
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.
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: x1 y1 x2 y2 x3 y3, ce reprezinta coordonatele celor trei colturi ale suprafetei triunghiulare detinute de un taran. (x1 x2 x3 abscise, iar y1 y2 y3 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).
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.
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.
Exemplu
| triunghi2.in | triunghi2.out |
|---|---|
| 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 |
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).
