Fişierul intrare/ieşire:	game2d.in, game2d.out	Sursă	Lot Vaslui 2014 Seniori Baraj 6
Autor	Andrei Cristian Lambru	Adăugată de	Marian Darius •dariusdarius
Timp execuţie pe test	1.5 sec	Limită de memorie	65536 kbytes
Scorul tău	N/A	Dificultate	N/A

Vezi solutiile trimise | Statistici

Game2d

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.

Date de intrare

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

Date de ieşire

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

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.

Exemplu

Cum se trimit solutii?