Poligon

poligon

==Include(page="template/taskheader" task_id="poligon")==

== include(page="template/taskheader" task_id="poligon") ==
 
Poveste ...
 
h2. Cerinta
 
...
 
h2. Restrictii
 
...
 
h2. Date de intrare
 
...
 
h2. Date de iesire
 
...
 
h2. Exemplu
 
| poligon.in | poligon.out |
| linia1
linia2
linia3
| linia1
linia2
|
 
== include(page="template/taskfooter" task_id="poligon") ==

==Include(page="template/raw")==
 
Link: [1]File-List
 
poligon
 
 
 
Dupa o noapte dementa, plina de infractiuni, un ofiter de politie lucreaza la elaborarea unor statistici. El are in fata harta orasului cu punctele unde s-au intamplat infractiuni precum si o zona in forma de poligon (nu neaparat convex) din harta care prezinta interes maxim.
 
h2. Cerinta
 
Fiind dat poligonul ce descrie zona de interes si punctele infractionale trebuie sa aflati numarul de infractiuni petrecute in acea zona.
 
h2. Date de Intrare (fisier: poligon.in)
 
In fisierul de intrare se vor afla pe prima linie numerele intregi N si M separate printr-un spatiu, N e numarul de varfuri ale zonei poligonale iar M numarul total de infractiuni desfasurate noaptea trecuta. Pe urmatoarele N linii se vor afla cate doi intregi reprezentand coordonatele varfurilor poligonului date in ordinea parcurgerii lor mergand numai intr-o directie (din cele doua posibile) pe laturile sale. Pe urmatoarele M linii se vor afla coordonatele infractiunilor desfasurate in noaptea anterioara.
 
h2. Date de Iesire (fisier: poligon.out)
 
In fisierul de iesire se va afla pe prima linie numarul de puncte interioare sau pe marginea zonei date. Linia se termina cu caracterul "end of line".
 
h2. Restrictii
 
S 3 <= N <= 800
 
S 1 <= M <= 60.000
 
S Coordonatele punctelor vor fi numere intregi intre 0 si 60.000
 
S Poligonul nu se auto-intersecteaza
 
h2. Exemplu
 
poligon.in poligon.out
4 3 2
 
0 0
 
0 100
 
100 100
 
100 0
 
50 50
 
100 50
 
100 110
 
 
 
References
 
Visible links
1. file:///home/eval/eval/www/infoarena/docs/arhiva/poligon/enunt_files/filelist.xml
==Include(page="template/taskfooter" task_id="poligon")==