== include(page="template/taskheader" task_id="robot") ==
==Include(page="template/taskheader" task_id="robot")==
Poveste ...
Gigel tocmai si-a cumparat un joc de strategie. Actiunea jocului ia loc pe o harta plana. Pe harta se gaseste un mic robotel si cateva obstacole. Scopul jocului este de a muta robotelul intr-un anumit loc. Fiindca nu se pricepe prea bine la jocuri pe calculator, Gigel va roaga sa-l ajutati.
h2. Cerinta
Robotelul si obstacolele sunt reprezentate de poligoane convexe, cu varfurile in puncte de coordonate intregi. Spunem ca robotelul se afla intr-o pozitie valida pe harta daca poligonul care il reprezinta nu se intersecteaza cu interiorul nici unui obstacol. Daca robotelul este tangent la unul sau mai multe obstacole, fara a intersecta insa interiorul nici unuia dintre ele, pozitia lui este valida.
Pe tot parcursul jocului obstacolele raman nemiscate si nerotite. De asemenea, robotelul nu se poate roti, insa acesta se poate misca in orice directie. Pe tot parcursul miscarii sale, robotelul trebuie sa ramana intr-o pozitie valida.
...
Pozitia robotelului pe harta se defineste ca fiind punctul ({$x,y$}), cu $y$ egal cu minimul ordonatelor varfurilor robotelului si cu $x$ egal cu minimul absciselor varfurilor robotelului. Curba desenata de pozitia robotelului in timpul miscarii sale in plan se numeste drumul robotelului.
h2. Restrictii
h2. Cerinta
...
Scrieti un program care citeste configuratia initiala a hartii si care calculeaza lungimea unui drum minim parcurs de robotel pentru a ajunge intr-o pozitie finala.
h2. Date de intrare
...
Pe prima linie a fisierului de intrare $robot.in$ se gaseste numarul $N$ de varfuri ale poligonului reprezentand robotelul. Pe urmatoarele $N$ linii se gasesc coordonatele $x$ si $y$ ale varfurilor robotelului, coordonate separate printr-un spatiu. Pe urmatoarea linie se gaseste numarul $M$ de obstacole. Apoi urmeaza $M$ blocuri reprezentand cate un obstacol, fiecare bloc avand urmatoarea structura:
* pe prima linie a blocului numarul de varfuri $P$ ale poligonului ce reprezinta obstacolul
* pe urmatoarele $P$ linii, coordonatele $x$ si $y$ ale varfurilor obstacolului, coordonate separate printr-un spatiu.
Pe ultima linie a fisierului de intrare, se gasesc coordonatele $x$ si $y$ ale pozitiei in care trebuie sa ajunga robotelul.
h2. Date de iesire
...
Pe singura linie a fisierului de iesire $robot.out$ afisati cu doua zecimale exacte distanta minima parcursa de robot pana la pozitia finala pe un drum care respecta cerintele de mai sus. Daca nu exista nici un astfel de drum afisati {$-1$}.
h2. Restrictii si precizari
* $N ≤ 10$
* $M ≤ 25$
* toate coordonatele sunt din intervalul ({$-5000,5000$})
* numarul de varfuri de pe poligoanele tuturor obstacolelor nu depaseste $250$
* puteti presupune ca pozitia initiala a robotelului este valida.
* in fisierul de intrare, pentru toate poligoanele, punctele sunt date in sens trigonometric.
* solutia afisata de voi este considerata corecta daca difera de solutia comisiei in valoare absoluta prin cel mult $0.02$
* unii sustin ca adevaratul campion este cel care rezolva *ivv* adevarul este insa ca singurul care poate determina adevaratul campion este robotelul
h2. Exemplu
| robot.in | robot.out |
| linia1
linia2
linia3
| linia1
linia2
|
table(example). |_. robot.in |_. robot.out |
| 3
0 0
2 0
0 2
1
4
3 0
5 0
5 2
3 2
6 2
| 7.24 |
== include(page="template/taskfooter" task_id="robot") ==
h3. Explicatii
!problema/robot?robot.gif!
Robotelul apare punctat si obstacolul este desenat cu linie ingrosata. Cerculetul reprezinta pozitia finala a robotelului. Cu o linie usor ingrosata este marcat si un drum de lungime minima.
==Include(page="template/taskfooter" task_id="robot")==
