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.

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. 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 (fisier: robot.in)

h2. Date de intrare

Pe prima linie a fisierului de intrare 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 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 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.

- pe urmatoarele P linii, coordonatele x si y ale varfurilor obstacolului, coordonate separate printr-un spatiu.

h2. Date de iesire

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 (fisier: robot.out)
 
Pe singura linie a fisierului de iesire 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.

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

o N -L- 10, M -L- 25, toate coordonatele sunt din intervalul (-5000,5000)
o numarul de varfuri de pe poligoanele tuturor obstacolelor nu depaseste 250.
o puteti presupune ca pozitia initiala a robotelului este valida.
o in fisierul de intrare, pentru toate poligoanele, punctele sunt date in sens trigonometric.
o solutia afisata de voi este considerata corecta daca difera de solutia comisiei in valoare absoluta prin cel mult 0.02
o unii sustin ca adevaratul campion este cel care rezolva ivv; adevarul este insa ca singurul care poate determina adevaratul campion este robotelul.

* $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 Explicatie
3 7.24 Desenul alaturat este reprezentarea grafica a exemplului din stanga. 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.
 

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 |
 
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")==

390