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
Cunoscand punctul
in care se afla initial robotul, punctul destinatie si configuratia tuturor
obstacolelor, determinati consumul minim in litri kerosen cu care robotul poate
ajunge la destinatie.
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.
Exemplu
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:
