În satul vecin există un teren agricol de formă dreptunghiulară împărțit în N*M
pătrate elementare identice, dispuse alăturat câte M
pe fiecare rând şi câte N
pe fiecare coloană. Rândurile sunt numerotate de la 1
la N
, iar coloanele de la 1
la M
. Un pătrat elementar situat în teren pe rândul R
și coloana C
este identificat prin coordonatele (R,C)
.
Suprafețe dreptunghiulare din teren (formate fiecare din unul sau mai multe pătrate elementare alăturate) sunt revendicate de T
fermieri din sat, în calitate de moștenitori, pe baza actelor primite de la strămoșii lor. Pentru că au apărut și acte false, s-a constat că pot exista mai mulți fermieri care revendică aceleași pătrate elementare.
În cele T
acte ale fermierilor, suprafețele dreptunghiulare sunt precizate fiecare prin câte două perechi de numere (X,Y)
și (Z,U)
, reprezentând coordonatele primului pătrat elementar din colțul stânga-sus al suprafeței (rândul X
și coloana Y
), respectiv coordonatele ultimului pătrat elementar situat în colțul dreapta-jos al suprafeței (rândul Z
și coloana U
).
Cerinţe
Scrieţi un program care să citească numerele naturale N
, M
, T
, R
, C
apoi cele T
perechi de coordonate (X,Y)
și (Z,U)
precizate în acte (corespunzătoare suprafețelor dreptunghiulare revendicate) și care să determine:
- numărul fermierilor care revendică pătratul elementar identificat prin coordonatele
(R,C)
; - numărul maxim de fermieri care revendică același pătrat elementar;
- numărul maxim de pătrate elementare ce formează o suprafață pătratică nerevendicată de niciun fermier.
Date de intrare
Fişierul teren.in
conţine pe prima linie un număr natural P
care poate avea doar valoarea 1
, valoarea 2
sau valoarea 3
. Pe a doua linie a fișierului sunt scrise cinci numere naturale N
, M
, T
, R
, C
, separate prin câte un spaţiu, cu semnificaţia din enunţ. Pe fiecare din următoarele T
linii ale fișierului sunt câte patru numere naturale nenule X
K
, Y
K
, Z
K
, U
K
, separate prin câte un spaţiu, reprezentând perechile de coordonate (X
K
,Y
K
)
și (Z
K
,U
K
)
corespunzătoare terenurilor revendicate de cei T
fermieri (1 ≤ K ≤ T
).
Date de ieșire
Fişierul de ieşire teren.out
va conţine pe prima linie un număr natural reprezentând numărul fermierilor care revendică pătratul elementar identificat prin coordonatele (R,C)
dacă cerința a fost 1
, un număr natural reprezentând numărul maxim de fermieri ce revendică același pătrat elementar dacă cerința a fost 2
, respectiv un număr natural reprezentând numărul maxim de pătrate elementare ce formează o suprafață pătratică nerevendicată de niciun fermier dacă cerința a fost 3
.
Restricții și precizări
3 ≤ N, M ≤ 180
;3 ≤ T ≤ 100
;1 ≤ R ≤ N
;1 ≤ C ≤ M
;1 ≤ X
K
≤ Z
K
≤ N
şi1 ≤ Y
K
≤ U
K
≤ M
pentruK=1,2,3,...,T
;- Pentru rezolvare corectă a cerinţei 1 se acordă 20% din punctaj, pentru rezolvarea corectă a cerinţei 2 se acordă 20% din punctaj, iar pentru rezolvarea corectă a cerinței 3 se acordă 60% din punctaj.
Exemplul 1
teren.in
1 3 5 3 2 2 2 3 2 3 1 2 3 3 2 1 2 3
teren.out
2
Explicație
Pătratul elementar cu coordonatele R=2
și C=2
este revendicat de 2
fermieri.
Exemplul 2
teren.in
2 3 5 3 2 2 2 3 2 3 1 2 3 3 2 1 2 3
teren.out
3
Explicație
Pătratul elementar cu coordonatele (2,3)
este revendicat de 3
fermieri (numărul maxim de revendicări).
Exemplul 3
teren.in
3 3 5 3 2 2 2 3 2 3 1 2 3 3 2 1 2 3
teren.out
4
Explicație
Sunt două suprafețe pătratice nerevendicate de niciun fermier, formate fiecare din numărul maxim de patru pătrate elementare. Acestea au coordonatele: (1,4)
și (2,5)
respectiv (2,4)
și (3,5)
.
#include <bits/stdc++.h> using namespace std; ifstream cin("teren.in"); ofstream cout("teren.out"); int a[200][200] , n , m , t , r , c , x1 , x2 , y1 , y2 , cer , lmax , b[200][200]; void umplere(int x1 , int y1 , int x2 , int y2) { for(int i = x1 ; i <= x2 ; i++) for(int j = y1 ; j <= y2 ; j++) a[i][j]++; } int main() { cin >> cer; cin >> n >> m >> t >> r >> c; for(int i = 1 ; i <= t ; i++) { cin >> x1 >> y1 >> x2 >> y2; umplere(x1 , y1 , x2 , y2); } /*for(int i = 1 ; i <= n ; i++) { for(int j = 1 ; j <= m ; j++) cout << a[i][j] << " "; cout << '\n'; }*/ if(cer == 1) cout << a[r][c]; else if(cer == 2) { int maxi = 0; for(int i = 1 ; i <= n ; i++) { for(int j = 1 ; j <= m ; j++) if(a[i][j] > maxi) maxi = a[i][j]; } cout << maxi; } else { for(int i = 1 ; i <= n ; i++) { for(int j = 1 ; j <= m ; j++) if(a[i][j] == 0) { b[i][j] = min(min(b[i][j-1] , b[i-1][j]) , b[i-1][j-1]) + 1; lmax = max(lmax, b[i][j]); } } cout << lmax*lmax; } }