| 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 |  5/5 |
Vezi solutiile trimise | Statistici
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.
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, etc.).
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
Exemplu
| 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 |
