Fişierul intrare/ieşire:cabana2.in, cabana2.outSursăONI 2015, clasa a 10-a
AutorLiliana SchiopuAdăugată deharababurelPuscas Sergiu •harababurel
Timp execuţie pe test0.25 secLimită de memorie20480 kbytes
Scorul tăuN/ADificultateN/A

Vezi solutiile trimise | Statistici

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.

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.

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.

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

Restricţii

  • Pentru 10% din teste: 1 ≤ n ≤ 10, -103 ≤ x, y ≤ 103.
  • Pentru 30% din teste: 1 ≤ n ≤ 500, -103 ≤ x, y ≤ 103.
  • Pentru 50% din teste: 1 ≤ n ≤ 500, -106 ≤ x, y ≤ 106.
  • Pentru 70% din teste: 1 ≤ n ≤ 3000, -109 ≤ x, y ≤ 109.
  • Pentru 100% din teste: 1 ≤ n ≤ 50000, -109 ≤ x, y ≤ 109.
  • Nu există doi arbori aşezaţi pe aceeaşi poziţie.

Exemplu

cabana2.incabana2.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

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.

Trebuie sa te autentifici pentru a trimite solutii. Click aici

Cum se trimit solutii?