Mariuca
merge cu avionul pntru prima data. Din avion, ea vede terenuri cultivate de
forma dreptungiulara, având culori diferite, în functie de plantele
cultivate.
Mariuca ar vrea sa determine aria celui mai mare dreptunghi acoperit de plante
de aceeasi culoare.
Figurile de mai jos corespund celor 3 exemple, solutia fiind marcata în
figura.
Cerinta
Scrieti un program care sa determine aria celui mai mare dreptunghi cultivat
cu plante de aceeasi culoare.
Date
de intrare
Fisierul de intrare teren.in
contine pe prima linie un numar natural N
reprezentând numarul de terenuri vizibile. Fiecare dintre urmatoarele
N linii contine câte 5
numere întregi separate prin câte un spatiu X1
Y1 X2 Y2 C. (X1,Y1) si
(X2,Y2) reprezinta coordonatele
a doua colturi diagonal opuse ale terenului, iar C
reprezinta culoarea terenului.
Date de
iesire
Fisierul de iesire teren.out
va contine o singura linie pe care va fi scris un singur numar natural, reprezentând
aria celui mai mare dreptunghi cultivat cu plante de aceeasi culoare.
Restrictii
1 <= N <= 2500
1 <= C <= 100
0 <= X1, Y1, X2, Y2 <= 1 000 000 000
Oricare doua terenuri nu se suprapun (aria intersectiei lor este 0).
Solutia va fi un întreg pe 64 biti (int64 în Pascal, long long în
C/C++).
| teren.in | teren.out | teren.in | teren.out | teren.in | teren.out |
| 5
|
8 |
5
5 5 6 6 22 3 4 6 5 22 6 3 7 6 22 5 6 8 7 22 4 5 5 8 22 |
9 | 7
0 0 4 3 1 6 2 9 7 2 6 7 10 9 3 4 0 6 3 1 0 6 6 9 3 0 3 6 6 2 7 0 8 2 2 |
27 |
Timp
maxim de executie/test:
1.5 secunde
Memorie totala disponibila 32 Mb, din care 1 Mb pentru stiva.
prof.
Emanuela Cerchez
Liceul de
Informatica "Grigore Moisil" Iasi
Contact:emanuela.cerchez@gmail.com