Fişierul intrare/ieşire:patrate.in, patrate.outSursăLot 2005
AutorCosmin Silvestru NegruseriAdăugată de
Timp execuţie pe test0.075 secLimită de memorie65536 kbytes
Scorul tăuN/ADificultatenormalnormalnormalnormalnormal

Vezi solutiile trimise | Statistici

Patrate

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.

Cerinta

Ajutati-l pe Ion sa gaseasca o solutie care sa il multumeasca pe Vasile.

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

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.

Restrictii

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

Exemple

patrate.inpatrate.out
6
1 0
2 1
3 2
3 4
5 4
6 0
2

Explicatii

Trebuie sa te autentifici pentru a trimite solutii. Click aici

Cum se trimit solutii?

remote content