Fişierul intrare/ieşire:	tramvai.in, tramvai.out	Sursă	Happy Coding 2007
Autor	Mugurel Ionut Andreica	Adăugată de	Mugurel-Ionut Andreica •mugurelionut
Timp execuţie pe test	0.75 sec	Limită de memorie	128000 kbytes
Scorul tău	N/A	Dificultate	N/A

Vezi solutiile trimise | Statistici

Tramvai

Intr-un oras exista N lini de tramvai, fiecare din ele fiind reprezentata de o linie dreapta. Statiile in care tramvaiele opresc, pentru a putea urca si cobori calatorii, sunt construite numai la intersectiile a oricare doua linii de tramvai. Un calator se afla in statia de la intersectia dintre liniile LS1 si LS2 si doreste sa ajunga la statia de la intersectia liniilor LF1 si LF2, mergand numai cu tramvaiul si parcurgand o distanta cat mai mica.

Determinati lungimea minima a unui traseu cu tramvaiul intre cele doua statii.

Date de intrare

Pe prima linie a fisierului de intrare tramvai.in se afla numarul intreg N, reprezentand numarul de linii de tramvai existente in oras. Pe urmatoarele N linii se afla cate 4 numere intregi: x1 y1 x2 y2. (x1,y1) si (x2,y2) repezinta coordonatele a doua puncte distincte din plan, care determina in mod unic dreapta care corespunde unei linii de tramvai. Liniile sunt numerotate de la 1 la N, in ordinea in care apar in fisierul de intrare. Pe a N+2-a linie se afla inca patru numere intregi, separate prin spatii: LS1 LS2 LF1 LF2.

Date de iesire

In fisierul de iesire tramvai.out veti afisa lungimea minima a unui traseu intre cele doua statii, mergand numai de-a lungul liniilor de tramvai. Acest numar va fi afisat cu cel putin 3 zecimale. Se accepta o eroare de 0.001.

Restrictii

• 3 ≤ N ≤ 1000
• Coordonatele punctelor ce definesc liniile de tramvai sunt numere intregi din intervalul [0,1000].
• 1 ≤ LS1, LS2, LF1, LF2 ≤ 1000
• Liniile LS1 si LS2 nu vor fi paralele, nici identice.
• Liniile LF1 si LF2 nu vor fi paralele, nici identice.
• Pe fiecare linie, tramvaile circula in ambele sensuri.

Exemplu

Cum se trimit solutii?