Enunț
Scrierea numelor localităţilor pe o hartă a fost întotdeauna o problemă importantă a cartografilor, deoarece dacă unele nume s-ar suprapune harta ar deveni ilizibilă.
Se cunosc coordonatele carteziene ale punctelor care marchează pe hartă localităţile. Pentru fiecare localitate marcată pe hartă trebuie să scriem numele său. Numele unei localităţi trebuie să fie încadrat într-un dreptunghi care îndeplineşte următoarele condiţii:
- are laturile paralele cu axele de coordonate;
- lăţimea dreptunghiului este egală cu triplul înălţimii dreptunghiului;
- punctul care marchează pe hartă localitatea să fie plasat în colţul stânga sus al dreptunghiului.
Dreptunghiurile în care sunt scrise numele localităţilor trebuie să aibă toate aceleaşi dimensiuni.
Cerință
Scrieţi un program care să determine înălţimea maximă a dreptunghiului care încadrează numele localităţilor, astfel încât oricare două dreptunghiuri desenate pe hartă să aibă intersecţia de arie .
Date de intrare
Fişierul harta.in conţine pe prima linie un număr natural reprezentând numărul de localităţi marcate pe hartă. Pe fiecare dintre următoarele linii se află câte două numere naturale , reprezentând coordonatele punctelor (abscisă, ordonată) care marchează pe hartă localităţile.
Date de ieșire
Fişierul harta.out va conţine o singură linie pe care va fi scris un număr real cu zecimale care reprezintă lăţimea maximă a dreptunghiurilor care încadrează numele localităţilor, astfel încât oricare două dreptunghiuri să aibă intersecţia de arie .
Restricții și precizări
- ;
- ;
- Oricare două puncte de pe hartă sunt distincte.
- Rezultatul va fi considerat corect dacă diferenţa în valoare absolută dintre rezultatul corect şi cel din fişierul de ieşire este .
Exemplul 1
harta.in
5
1 1
6 5
18 3
9 9
16 15
harta.out
4.000
Exemplul 2
harta.in
10
26 77
12 37
14 18
19 96
71 95
91 9
98 43
66 77
2 75
94 91
harta.out
7.667