== include(page="template/taskheader" task_id="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$ ÅŸi $LS2$ ÅŸi doreste sa ajunga la statia de la intersectia liniilor $LF1$ si $LF2$, mergand numai cu tramvaiul si parcurgand o distanta cat mai mica.

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$.

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

0 0 0 1000
0 0 1000 0
0 1 1000 1

1 2 2 3

1 2 1 3

|1.000|
== include(page="template/taskfooter" task_id="tramvai") ==

2371