robot

Un robot zburator se afla intr-un plan la coordonate cunoscute. La fiecare pas, robotul se poate deplasa in zbor in orice directie, dar continuu in linie dreapta si nu se poate opri decat atunci cand intalneste un obstacol sau ajunge la destinatie. Obstacolele sunt cercuri in interiorul carora robotul nu poate intra, dar pe extremitatea carora poate merge liber pe pamant. Dupa ce ajunge pe un cerc si se deplaseaza eventual pe acesta, robotul trece la urmatorul pas si porneste din nou in zbor, iar, pana ajunge la alt obstacol sau la destinatie, si asa mai departe. Destinatia robotului este un punct cunoscut din plan. Asadar deplasarea robotului este o succesiune alternanta de zboruri in linie dreapta si deplasari in mers pe extremitatile obstacolelor. De fiecare data cand robotul porneste in zbor consuma 1 litru de kerosen, dar odata pornit el nu mai consuma nimic, indiferent de lungimea deplasarii in zbor sau eventual lungimea deplasarii in mers de dupa zbor.

Cerinta

Date de intrare

Pe prima linie a fisierului robot.in se gasesc cinci numere naturale separate prin spatii n, xs, ys, xf, yf. Numarul n reprezinta numarul de obstacole, (xs, ys) este punctul unde se afla initial robotul, (xf, yf) este punctul destinatie. Fiecare dintre urmatoarele n linii contine cate 3 numere naturale x, y, r, unde (x, y) este centrul unui obstacol, iar r este raza acestuia.

Date de iesire

Prima linie a fisierului robot.out va contine un singur numar natural reprezentand numarul minim de litri de kerosen folositi pentru deplasarea pana la punctul final.

Restrictii si precizari

• 0 <= n <= 150
• Toate coordonatele din fisierul de intrare si razele cercurilor sunt numere naturale <= 10000
• Daca traiectoria in zbor a robotului este tangenta la un cerc, el este obligat sa se opreasca pe acel cerc.
• Oricare ar fi doua cercuri, ele nu se intersecteaza, nu sunt unul in interiorul celuilalt, si nici un cerc nu contine punctul initial sau destinatia.
• Oricare ar fi trei cercuri, nu exista o nici dreapta care sa fie tangenta la toate cele trei cercuri.

robot.in	robot.out	Explicatie
2 2 2 16 6 6 4 3 12 5 2	3	Traiectoria robotului poate fi cea desenata cu rosu:

Timp maxim de executie/test: 0.5 secunde

stud. Paul Diac
Universitarea « Al. I Cuza », Iasi – Facultatea de Informatica
Contact:diac_paul@yahoo.com