Cabana2

cabana2

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

Ben are un teren pe care se află o pădure cu arbori seculari. Acolo vrea să-şi construiască o cabană, însă el fiind ecologist nu vrea să taie niciun arbore, ci vrea să găsească cea mai mare suprafaţă dreptunghiulară fără arbori. El caută o suprafaţă dreptunghiulară străjuită doar în colţuri de arbori şi cu laturile paralele cu axele de coordonate. Ben cunoaşte coordonatele tuturor arborilor din pădure şi vă roagă să-l ajutaţi să găsească aria dreptunghiului cu suprafaţă maximă care are arbori **doar** în cele patru colţuri.
 
!problema/cabana2?cabana2.png!
 
h2. Cerinţă
 
Cunoscând numărul arborilor din pădure şi coordonatele acestora, se cere să se determine aria dreptunghiului de suprafaţă maximă cu copaci doar în cele $4$ colţuri, unde Ben intenţionează să-şi construiască cabana.

Poveste şi cerinţă...

h2. Date de intrare

Fişierul de intrare $cabana2.in$ conţine pe prima linie un număr natural $n$, reprezentând numărul de arbori din pădure.
Pe fiecare dintre următoarele $n$ linii se află două numere întregi, separate printr-un spaţiu, ce reprezintă abscisa şi ordonata unui arbore.

Fişierul de intrare $cabana2.in$ ...

h2. Date de ieşire

În fişierul de ieşire $cabana2.out$ se scrie pe prima linie numărul natural a, reprezentând aria dreptunghiului de suprafaţă maximă.

În fişierul de ieşire $cabana2.out$ ...

h2. Restricţii

* $Pentru 10% din teste: 1 ≤ n ≤ 10, -10^3^ ≤ x, y ≤ 10^3^.$
* $Pentru 30% din teste: 1 ≤ n ≤ 500, -10^3^ ≤ x, y ≤ 10^3^.$
* $Pentru 50% din teste: 1 ≤ n ≤ 500, -10^6^ ≤ x, y ≤ 10^6^.$
* $Pentru 70% din teste: 1 ≤ n ≤ 3000, -10^9^ ≤ x, y ≤ 10^9^.$
* $Pentru 100% din teste: 1 ≤ n ≤ 50000, -10^9^ ≤ x, y ≤ 10^9^.$
* $Nu există doi arbori aşezaţi pe aceeaşi poziţie.$

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

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

| 22
6 25
25 22
15 5
23 23
6 7
11 16
11 20
10 22
6 16
12 6
7 19
10 19
10 14
7 14
7 7
18 14
18 7
10 7
19 19
29 19
29 4
19 4
| 150

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

|
h3. Explicaţie

Coordonatele dreptunghiului de arie maximă cu laturile paralele cu axele de coordonate şi care nu conţine arbori decât în colţuri sunt:
 
* $(19, 19),$
* $(29, 19),$
* $(29, 4),$
* $(19, 4).$
 
Aria maximă este $150$.

...

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