James Bond

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
0 0 10 0
0 0 10 10
10 0 10 10
6 4 2 1
0 0
10 10

20
0 0
10 0
10 10

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