regiuni2

Regiuni2

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

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

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.
 
The first line of input contains the number T of test cases. The next lines describe the T test cases. The first line of each test case contains two integer numbers, separated by one blank:  the number N of vertices of the convex polygon (3 <= N <= 10) and the number M of straight lines (0 <= M <= 10). The next N lines contain 2 integer numbers X and Y, denoting the coordinates of some vertex of the polygon. The vertices are given in clockwise or anti-clockwise order.  Each of the next M lines contains 4 integer numbers: x1 y1 x2 y2. (x1,y1) and (x2,y2) are two different points on the straight line. All the X and Y coordinates in the input file are in the range -20…20.

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

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

2175