regiuni2

Regiuni2

== include(page="template/taskheader" task_id="regiuni2") ==

Poveste si cerinta...

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.

h2. 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: {$x{~1~} y{~1~} x{~2~} y{~2~}$}; $(x{~1~},y{~1~})$ si $(x{~2~},y{~2~})$ sunt $2$ puncte diferite de pe o dreapta.

h2. Date de iesire

...

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

h2. Restrictii

* $... ≤ ... ≤ ...$

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

h2. Exemplu
table(example). |_. regiuni2.in |_. regiuni2.out |

| This is some
  text written on
  multiple lines.
| This is another
  text written on
  multiple lines.

|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

|

h3. Explicatie
 
...
 

== include(page="template/taskfooter" task_id="regiuni2") ==

2175