==Include(page="template/taskheader" 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
==Include(page="template/taskheader" task_id="tri2")==
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, etc.).
h2. Restrictii si precizari
* $3 ≤ N ≤ 1 000$
* $1 ≤ M ≤ 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
table(example). |_. tri2.in|_. tri2.out|
|5
0 0
1 10
2 4
3 7
10 1
3
1 2 3
5 1 2
5 3 2
|0
2
1|
==Include(page="template/taskfooter" task_id="tri2")==
5 3 2
==Include(page="template/taskfooter" task_id="tri2")==
