# PBinfo #1218 – Teren – Rezolvare C++

Sursa: Codul lui Andrei
Limbaj: C++
Autor rezolvare: Darius

## Enunț

Î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 XK, YK, ZK, UK, separate prin câte un spaţiu,  reprezentând perechile de coordonate (XK,YK) și (ZK,UK) 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 ≤ XK ≤ ZK ≤ N  şi 1 ≤ YK ≤ UK ≤ M pentru K=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).

## Cod sursă C++

```cpp
//autor Carmen Minca - 100p
#include <fstream>
using namespace std;
int a[185][185];
ifstream f("teren.in");
ofstream g("teren.out");
int main()
{int n,t,m, r,c,i,j,p,nrb=0,nrc=0,x,y,z,u,k,lat,ok,nr;
f>>p>>n>>m>>t>>r>>c;
for(k=1;k<=t;k++)
{  f>>x>>y>>z>>u;
   for(i=x;i<=z;i++)
        for(j=y;j<=u;j++)
        {a[i][j]++;
         nrb=max(nrb,a[i][j]);}
}
if(p==1) g<<a[r][c]<<'\n';///cerinta 1
else if(p==2)g<<nrb<<'\n';  ///cerinta 2
else{
///cerinta 3
for(i=1;i<=n-nrc; i++)
    for(j=1;j<=m-nrc;j++)
      if(a[i][j]==0)
        { lat=1; ok=1;
          while(ok)
            {x=z=lat+i;y=u=lat+j;
             if(x>n || y>m)ok=0;
             while(z>=i && ok )
              { if(a[x][u]+a[z][y]==0){u--; z--;}
                else ok=0;
              }
             if(ok)lat++;
            }
          nrc=max(lat, nrc);
        }
g<<nrc*nrc<<'\n';}
return 0;
}
```

## Resurse

- [Pagina originală](https://codulluiandrei.ro/rezolvari/pbinfo/1218)
- [Sursa C++](https://codulluiandrei.ro/rezolvari/pbinfo/1218/cod.cpp)
- [Sursa pe GitHub](https://raw.githubusercontent.com/codulluiandrei/pbinfo/main/pbinfo-1218/main.cpp)
- [Cursuri de informatică pentru BAC](https://codulluiandrei.ro/academia/info-curs/pachet-cpp/)