Revizia anterioară Revizia următoare
Fişierul intrare/ieşire: | tri2.in, tri2.out | Sursă | Lot 2003 |
Autor | Mugurel Ionut Andreica | Adăugată de | |
Timp execuţie pe test | 0.5 sec | Limită de memorie | 65536 kbytes |
Scorul tău | N/A | Dificultate |
Vezi solutiile trimise | Statistici
Tri2
Aceasta pagina a fost importata din infoarena1 si nu este inca prelucrata. Sterge ==Include(file="template/raw")== cand esti multumit cu continutul paginii. |
---|
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.
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.
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.
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).
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
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