Nemo s-a hotarât să realizeze un joc pentru prietenii lui. Pentru că nu are cunoştinţe de grafică , a decis să realizeze un joculeţ . În sistemul de axe el desenează 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 și respectiv . Scopul jocului este găsirea distanței minime de la punctul la punctul ocolind interioarele dreptunghiurilor, dar putând merge pe frontiera acestora. Deoarece Nemo nu are astfel de cunoştinţe, vă oferă vouă de puncte dacă jucați acest joc pentru el.
Date de intrare
Pe prima linie a fişierului game2d.in se află valoarea reprezentând numărul de dreptunghiuri. Pe a doua linie se vor afla cele patru numere . Pe următoarele linii se vor afla coordonatele câte unui dreptunghi dat prin colţul din stânga sus şi colţul din dreapta jos .
Date de ieșire
Pe prima şi singura linie a fişierului game2d.out se va scrie un număr real cu zecimale ce reprezintă distanţa minimă cerută.
Restricții si precizări
- (pentru orice coordonate ce apar în datele problemei)
- Se garantează că oricare două dreptunghiuri nu se intersectează în niciun punct.
- Se garantează că punctul de start şi cel de final sunt în exteriorul oricărui dreptunghi.
- Aria oricărui dreptunghi nu va depăşi
- Se acordă punctaj maxim doar dacă diferenţa dintre rezultatul vostru şi rezultatul corect este mai mică decât .
- Nemo vă sfătuieşte să folosiţi la implementare tipurile
long longşidouble.
Exemplul 1
game2d.in
2
1 1 4 5
1 5 2 4
4 2 5 1
game2d.out
5.000000
Explicație
Distanţa minimă dintre punctul de coordonate și cel de coordonate este chiar distanţa dintre cele puncte.
Exemplul 2
game2d.in
4
6 5 1 1
5 4 6 3
2 4 4 2
2 6 4 5
1 8 2 7
game2d.out
6.812559
Exemplul 3
game2d.in
3
1 4 4 4
1 2 4 1
2 5 3 3
1 7 4 6
game2d.out
3.828427
Exemplul 4
game2d.in
4
1 9 8 1
2 3 3 1
6 3 7 1
4 5 5 2
1 7 8 6
game2d.out
12.187601
Exemplul 5
game2d.in
4
1 1 5 6
1 5 2 4
2 3 3 2
3 5 4 4
4 2 5 1
game2d.out
6.708204