harta2

Harta2

== include(page="template/taskheader" task_id="harta2") ==

Poveste si cerinta...

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.
 
h2. 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$}.

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

h2. 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$}.

h2. Restrictii

* $... ≤ ... ≤ ...$

* {$1 < N &le; 1.000.000$}
* {$0 &le; X, Y &le; 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$}.

h2. Exemplu
table(example). |_. harta2.in |_. harta2.out |

| This is some
  text written on
  multiple lines.
| This is another
  text written on
  multiple lines.

| 5
1 1
6 5
18 3
9 9
16 15
| 4.000

|

 
h3. Explicatie
 
...

| 10
26 77
12 37
14 18
19 96
71 95
91 9
98 43
66 77
2 75
94 91
| 7.667
|

== include(page="template/taskfooter" task_id="harta2") ==

1967