patrate

Patrate

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

==Include(page="template/taskheader" task_id="patrate")==

Poveste ...

Ciobanasul Ion vrea sa isi inchida oile in tarcuri si printr-o coincidenta fericita prietenul lui, Vasile are o firma de construit tarcuri. Cum Vasile este bun prieten cu Ion i-a propus sa ii construiasca tarcurile gratis, cu conditia ca ele sa aiba un cost cat mai mic. Vasile accepta sa construiasca cel mult trei tarcuri de forma unor patrate cu laturile paralele cu axele de coordonate. Aceste patrate trebuie sa contina in interior toate oile, consideram pentru simplitate ca o oaie este un punct in plan. Pentru a obtine un cost cat mai mic, trebuie ca latura celui mai mare tarc sa fie cat mai scurta posibil. Tarcurile se pot intersecta, iar un punct de pe marginea tarcului se considera in interior.

h2. Cerinta

...

Ajutati-l pe Ion sa gaseasca o solutie care sa il multumeasca pe Vasile.
 
h2. Date de intrare
 
In fisierul de intrare $patrate.in$ se afla pe prima linie un numar natural $n$ ce reprezinta numarul oilor lui Ion, iar pe urmatoarele $n$ linii pozitiile oilor, adica fiecare astfel de linie contine doua numere intregi $x, y$ separate printr-un singur spatiu ce reprezinta pozitia unei oi (abscisa si ordonata).
 
h2. Date de iesire
 
Fisierul de iesire $patrate.out$ va contine un numar natural ce reprezinta latura minima care o poate avea cel mai mare tarc dintre cele trei, astfel incat toate oile sa fie in interiorul celor trei tarcuri.

h2. Restrictii

...

* $1≤n≤50000$
* Coordonatele oilor sunt numere intregi din intervalul $[0, 50000]$

h2. Date de intrare

h2. Exemple

...

table(example). |_. patrate.in |_. patrate.out |
|6
1 0
2 1
3 2
3 4
5 4
6 0
| 2 |

h2. Date de iesire

h3. Explicatii

...

!problema/patrate?image001.gif!

h2. Exemplu

==Include(page="template/taskfooter" task_id="patrate")==

| patrate.in | patrate.out |
| linia1
linia2
linia3
| linia1
linia2
|
== include(page="template/taskfooter" task_id="patrate") ==

388