Revizia anterioară Revizia următoare
| Fişierul intrare/ieşire: | regiuni2.in, regiuni2.out | Sursă | Selectie echipe ACM ICPC, UPB 2007 |
| Autor | Mugurel Ionut Andreica | Adăugată de |  Mugurel-Ionut Andreica •mugurelionut |
| Timp execuţie pe test | 0.025 sec | Limită de memorie | 67583 kbytes |
| Scorul tău | N/A | Dificultate | N/A |
Vezi solutiile trimise | Statistici
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.
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} y{~1 x2 y2; (x1,y1) si $(x2,y2) 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 ×2 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.
Date de iesire
...
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.in | regiuni2.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 |
