Fişierul intrare/ieşire:harta2.in, harta2.outSursăLot Alba 2007
AutorEmanuela CerchezAdăugată deDITzoneCAdrian Diaconu DITzoneC
Timp execuţie pe test0.5 secLimită de memorie36864 kbytes
Scorul tăuN/ADificultateN/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.inharta2.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
Trebuie sa te autentifici pentru a trimite solutii. Click aici

Cum se trimit solutii?

remote content