Tri2

tri2

==Include(page="template/taskheader" task_id="tri2")==

== include(page="template/taskheader" task_id="tri2") ==
 
Poveste ...
 
h2. Cerinta
 
...
 
h2. Restrictii
 
...
 
h2. Date de intrare
 
...
 
h2. Date de iesire
 
...
 
h2. Exemplu
 
| tri2.in | tri2.out |
| linia1
linia2
linia3
| linia1
linia2
|
 
== include(page="template/taskfooter" task_id="tri2") ==

==Include(page="template/raw")==
 
Tri 2
 
 
 
Micutul Gigel a marcat pe hartie N puncte, avand coordonate intregi. Apoi a inceput sa deseneze triunghiuri, avand varfurile in trei puncte diferite dintre cele N. Pentru fiecare triunghi desenat, Gigel ar dori sa stie cate dintre cele N-3 puncte ramase se afla strict in interiorul triughiului.
 
h2. Cerinta
 
Pentru fiecare triunghi dat (prin indicii celor 3 puncte care sunt varfurile sale), determinati cate dintre celelalte puncte se afla strict in interiorul triunghiului.
 
h2. Date de Intrare
 
Pe prima linie a fisierului de intrare tri2.in se afla numarul intreg N, reprezentand numarul de puncte marcate de Gigel pe hartie. Pe fiecare dintre urmatoarele N linii se afla coordonatele fiecarui punct, in ordine, de la cel numerotat cu 1, la cel numerotat cu N. Coordonatele sunt descrise prin doi intregi x si y, separati printr-un spatiu. Urmatoarea linie contine numarul intreg M de triunghiuri pe care le-a desenat Gigel. Pe urmatoarele M linii se afla cate trei numere intregi, a, b si c, separate prin spatii, reprezentand indicii a trei puncte diferite dintre cele N.
 
h2. Date de Iesire
 
In fisierul de iesire tri2.out veti afisa M linii. Pe fiecare linie se va afla un numar intreg, reprezentand numarul de puncte dintre cele N-3 ramase, care se afla strict in interiorul triunghiului corespunzator liniei (prima linie va contine raspunsul corespunzator primului triunghi descris in fisierul de intrare, a doua linie raspunsul corespunzator celui de-al doilea triunghi s.a.m.d).
 
h2. Restrictii si precizari
 
. 3 -L- N -L- 1.000
 
. 1 -L- M -L- 500.000
 
. Coordonatele x, y sunt numere intregi din intervalul [0,2.000.000.000]
 
. Oricare doua puncte au coordonatele x, respectiv y, distincte
 
. Oricare trei puncte sunt necoliniare
 
. Daca doriti sa folositi numere reale in programul vostru, se recomanda folosirea tipurilor long double pt. C/C++, respectiv extended pt. Pascal. Pentru testarea egalitatii a doua numere reale se recomanda folosirea unei precizii de 10^-14
 
h2. Exemplu
 
tri2.in tri2.out
5 0
 
0 0 2
 
1 10 1
 
2 4
 
3 7
 
10 1
 
3
 
1 2 3
 
5 1 2
 
5 3 2
 
 
==Include(page="template/taskfooter" task_id="tri2")==