Fişierul intrare/ieşire:regiuni.in, regiuni.outSursăpreONI 2007, Runda 4
AutorCosmin Silvestru NegruseriAdăugată deCosminCosmin Negruseri Cosmin
Timp execuţie pe test0.1 secLimită de memorie5120 kbytes
Scorul tăuN/ADificultatenormalnormalnormalnormalnormal

Vezi solutiile trimise | Statistici

Regiuni

Se dau n drepte si m puncte in plan. Nici un punct nu va fi pe vreo dreapta. Dreptele impart planul in regiuni. Spunem ca doua puncte sunt in aceiasi regiune daca nu exista vreo dreapta care sa le desparta. Se cere sa afisati numarul de grupuri de puncte, fiecare grup continand toate punctele din aceiasi regiune.

Date de intrare

Pe prima linie a fisierului de intrare vor fi n si m separate prin un spatiu. Urmatoarele n linii vor contine cate 3 numere intregi a, b, c ce vor reprezenta coeficientii ecuatiei dreptei ax + by + c = 0. Urmatoarele m linii vor contine doi intregi separati prin spatiu ce reprezinta coordonatele punctelor.

Date de iesire

Numarul de grupuri de puncte.

Restrictii

  • 1 ≤ n, m ≤ 1000
  • Coordonatele punctelor si coeficientii dreptelor vor fi intre -30000 si 30000.

Exemplu

regiuni.inregiuni.out
3 5
0 1 -1
1 0 -2
1 1 -6
1 3
1 4
3 2
5 3
6 3
3

Explicatie

Primele doua puncte formeaza un grup, urmatorul punct inca un grup iar ultimele 2 puncte formeaza al treilea grup.

Trebuie sa te autentifici pentru a trimite solutii. Click aici

Cum se trimit solutii?

remote content