Fişierul intrare/ieşire:regiuni2.in, regiuni2.outSursăSelectie echipe ACM ICPC, UPB 2007
AutorMugurel Ionut AndreicaAdăugată demugurelionutMugurel-Ionut Andreica mugurelionut
Timp execuţie pe test0.025 secLimită de memorie67583 kbytes
Scorul tăuN/ADificultateN/A

Vezi solutiile trimise | Statistici

Regiuni2

Se da un poligon convex cu N varfuri si M drepte care impart poligonul in regiuni. Calculati numarul de regiuni in care este impartit poligonul de catre cele M drepte date.

Date de intrare

Prima linie a fisierului de intrare regiuni2.in contine numarul T de teste continute in fisier. Prima linie a fiecarui test contine 2 numere intregi, separate printr-un spatiu: numarul N de varfuri ale poligonului si numarul M de drepte. Urmatoarele N linii contin cate 2 numere intregi X si Y, reprezentand coordonatele unui varf al poligonului. Varfurile sunt date in odinea in care sunt asezate pe conturul poligonului (in sens trigonometric sau in sens invers trigonometric). Fiecare din urmatoarele M linii contine cate 4 numere intregi: x1 y1 x2 y2; (x1,y1) si (x2,y2) sunt 2 puncte diferite de pe o dreapta. 

Date de iesire

Pentru fiecare test din fisierul de intrare afisati o linie care contine numarul de regiuni in care este impartit poligonul.

Restrictii

  • 1 ≤ T ≤ 11
  • 3 ≤ N ≤ 10
  • 0 ≤ M ≤ 10
  • Toate coordonatele X si Y din fisierul de intrare sunt in intervalul [-20,20].

Exemplu

regiuni2.inregiuni2.out
2
3 0
0 0
1 1
1 0
3 3
0 0
1 1
1 0
1 2 3 4
1 2 3 4
1 2 3 4
1
1
Trebuie sa te autentifici pentru a trimite solutii. Click aici

Cum se trimit solutii?

remote content