== include(page="template/taskheader" task_id="game2d") ==
Poveste şi cerinţă...
Nemo s-a hotarât să realizeze un joc pentru prietenii lui. Pentru că nu are cunoştinţe de grafică 3D, a decis să realizeze un joculeţ 2D. În sistemul de axe XOY el desenează $N$ dreptunghiuri nedegenerate care au colţurile de coordonate întregi, iar laturile sunt paralele cu axele de coordonate. De asemenea, în acest sistem are două puncte de coordonate întregi $(xS, yS)$ şi respectiv $(xF, yF)$. Scopul jocului este găsirea distanţei minime de la punctul $(xS, yS)$ la punctul $(xF, yF)$ ocolind interioarele dreptunghiurilor, dar putând merge pe frontiera acestora. Deoarece Nemo nu are astfel de cunoştinţe, vă oferă vouă $100$ de puncte dacă jucaţi acest joc pentru el.
h2. Date de intrare
Fişierul de intrare $game2d.in$ ...
Pe prima linie a fişierului $game2d.in$ se află valoarea $N$ reprezentând numărul de dreptunghiuri. Pe a doua linie se vor afla cele patru numere $xS, yS, xF, yF$. Pe următoarele $N$ linii se vor afla coordonatele câte unui dreptunghi dat prin colţul din stânga sus $(xST, yST)$ şi colţul din dreapta jos $(xDR, yDR)$.
h2. Date de ieşire
În fişierul de ieşire $game2d.out$ ...
Pe prima şi singura linie a fişierului $game2d.out$ se va scrie un număr real cu $6$ zecimale ce reprezintă distanţa minimă cerută.
h2. Restricţii
* $... ≤ ... ≤ ...$
* $1 ≤ N ≤ 750$
* $1 ≤ x, y ≤ 2 000 000 000$ (pentru orice coordonate ce apar in datele problemei)
* Se garanteaza ca oricare 2 dreptunghiuri nu se intersecteaza in nici un punct.
* Se garanteaza ca punctul de start si punctul de final sunt in exteriorul oricarui dreptunghi.
* Aria oricarui dreptunghi nu va depasi $10 000 000$.
* Se acorda maxim doar dacă diferenţa dintre rezultatul vostru şi rezultatul corect este mai mică decât $0.000001$.
h2. Exemplu
table(example). |_. game2d.in |_. game2d.out |
| This is some
text written on
multiple lines.
| This is another
text written on
multiple lines.
|
| 2
1 1 4 5
1 5 2 4
4 2 5 1
| 5.000000 |
| 4
6 5 1 1
5 4 6 3
2 4 4 2
2 6 4 5
1 8 2 7
| 6.812559 |
| 3
1 4 4 4
1 2 4 1
2 5 3 3
1 7 4 6
| 3.828427 |
| 4
1 9 8 1
2 3 3 1
6 3 7 1
4 5 5 2
1 7 8 6
| 12.187601 |
| 4
1 1 5 6
1 5 2 4
2 3 3 2
3 5 4 4
4 2 5 1
| 6.708204 |
h3. Explicaţie
...
== include(page="template/taskfooter" task_id="game2d") ==
