Fişierul intrare/ieşire:robot.in, robot.outSursăLot 2005
AutorStefan CiobacaAdăugată de
Timp execuţie pe test1.825 secLimită de memorie65536 kbytes
Scorul tăuN/ADificultatenormalnormalnormalnormalnormal

Vezi solutiile trimise | Statistici

Robot

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.

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.

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.

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.

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.

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

Exemplu

robot.inrobot.out
3
0 0
2 0
0 2
1
4
3 0
5 0
5 2
3 2
6 2
7.24

Explicatii

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.

Trebuie sa te autentifici pentru a trimite solutii. Click aici

Cum se trimit solutii?

remote content