Revizia anterioară Revizia următoare
| 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 &le 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
| game2d.in | game2d.out |
|---|---|
| 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 |
Explicaţie
...
