Un grup de teroristi s-a ascuns într-un sistem de canalizare. James Bond, având la dispozitie o harta care descrie configuratia sistemului de canalizare si pozitiile în care teroristii au amplasat bombe, vrea sa anihileze grupul de teroristi.
Conductele din acest sistem sunt desenate pe harta sub forma unor segmente de dreapta în plan, astfel încât oricare doua segmente au cel mult un punct comun, care este capat pentru amândoua segmentele.
Explozia unei bombe afecteaza o zona circulara (interior si frontiera) si este instantanee pe întreaga zona afectata. Bombele pot sa difere una de cealalta prin raza de actiune sau prin timpul la care explodeaza. În urma unei explozii, canalele care trec prin zona de actiune a bombei devin impracticabile pe segmentul afectat, dar, daca Bond se afla într-un astfel de canal si a trecut deja de zona afectata de explozie, poate sa-si continue drumul. Daca James Bond se afla în raza de actiune a unei bombe la momentul exploziei, el moare!
La momentul initial (momentul 0), James Bond porneste dintr-un punct al sistemului de canalizare (capat al unui segment) si se deplaseaza cu viteza constanta, egala cu 1. James Bond trebuie sa ajunga în punctul în care se afla teroristii (capat al unui segment) în cel mai scurt timp posibil.
Cerinta
Determinati calea pe care trebuie s-o urmeze James Bond astfel încât sa ajunga viu la teroristi în cel mai scurt timp.
Date de intrare
Fisier de intrare: BOND.IN
Linia 1: M N
Liniile 2..M+1: X1 Y1 X2 Y2
Liniile M+2..M+N+1: XC YC R T
Linia M+N+2: XP YP
Linia M+N+3: XD YD
Date de iesire
Fisier de iesire: BOND.OUT
Linia 1: TMIN
Liniile 2...: C1 C2
Restrictii
Exemplu
BOND.IN |
BOND.OUT |
3 1 |
20 |
Observatii
În procesul de verificare se vor lua în considerare partea întreaga si primele 2 cifre zecimale.
Pentru datele de test se garanteaza existenta solutiei.
Datele de intrare sunt corecte.
Timp maxim de executare/test: 1 secunda