Fişierul intrare/ieşire:tri2.in, tri2.outSursăLot 2003
AutorMugurel Ionut AndreicaAdăugată de
Timp execuţie pe test1 secLimită de memorie65536 kbytes
Scorul tăuN/ADificultatenormalnormalnormalnormalnormal

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.intri2.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
Trebuie sa te autentifici pentru a trimite solutii. Click aici

Cum se trimit solutii?

remote content