== include(page="template/taskheader" task_id="tramvai") ==
Poveste si cerinta...
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.
h2. 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$.
h2. 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$.
h2. 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.
h2. Exemplu
table(example). |_. tramvai.in |_. tramvai.out |
| This is some
text written on
multiple lines.
| This is another
text written on
multiple lines.
|
h3. Explicatie
...
|3
0 0 0 1000
0 0 1000 0
0 1 1000 1
1 2 1 3
|1.000|
== include(page="template/taskfooter" task_id="tramvai") ==
