| Fişierul intrare/ieşire: | harta2.in, harta2.out | Sursă | Lot Alba 2007 |
| Autor | Emanuela Cerchez | Adăugată de |  Adrian Diaconu •DITzoneC |
| Timp execuţie pe test | 0.25 sec | Limită de memorie | 36864 kbytes |
| Scorul tău | N/A | Dificultate | N/A |
Vezi solutiile trimise | Statistici
Harta2
Scrierea numelor localitatilor pe o harta a fost intotdeauna o problema importanta a cartografilor, deoarece daca unele nume s-ar suprapune harta ar deveni ilizibila.
Se cunosc coordonatele carteziene ale punctelor care marcheaza pe harta localitatile. Pentru fiecare localitate marcata pe harta trebuie sa scriem numele sau. Numele unei localitati trebuie sa fie incadrat intr-un dreptunghi care indeplineste urmatoarele conditii:
- are laturile paralele cu axele de coordonate;
- lungimea dreptunghiului este egala cu triplul inaltimii dreptunghiului;
- punctul care marcheaza pe harta localitatea sa fie plasat in coltul stanga sus al dreptunghiului.
Dreptunghiurile in care sunt scrise numele localitatilor trebuie sa aiba toate aceleasi dimensiuni.
Cerinta
Scrieti un program care sa determine inaltimea maxima a dreptunghiului care incadreaza numele localitatilor, astfel incat oricare doua dreptunghiuri desenate pe harta sa aiba intersectia de arie 0.
Date de intrare
Fisierul harta2.in contine pe prima linie un numar natural N reprezentand numarul de localitati marcate pe harta. Pe fiecare dintre urmatoarele N linii se afla cate doua numere naturale X Y, reprezentand coordonatele punctelor (abscisa, ordonata) care marcheaza pe harta localitatile.
Date de iesire
Fisierul harta2.out va contine o singura linie pe care va fi scris un numar real cu 3 zecimale care reprezinta inaltimea maxima a dreptunghiurilor care incadreaza numele localitatilor, astfel incat oricare doua dreptunghiuri sa aiba intersectia de arie 0.
Restrictii
- 1 < N ≤ 1.000.000
- 0 ≤ X, Y ≤ 1.000.000
- Oricare doua puncte de pe harta sunt distincte.
- Rezultatul va fi considerat corect daca diferenta in valoare absoluta dintre rezultatul corect si cel din fisierul de iesire este <0.01.
Exemplu
| harta2.in | harta2.out |
|---|---|
| 5 1 1 6 5 18 3 9 9 16 15 | 4.000 |
| 10 26 77 12 37 14 18 19 96 71 95 91 9 98 43 66 77 2 75 94 91 | 7.667 |
