# PBinfo #3389 – colturi_dr – Rezolvare C++

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

## Enunț

Cerința
Se dă o matrice cu n linii și m coloane cu valori de 0 și 1. Numim dreptunghi de extrem un dreptunghi ale cărui vârfuri au valori egale. Determinați numărul acestor dreptunghiuri, aria dreptunghiului de arie maximă și câte dreptunghiuri au aceeași valoare a vârfurilor ca și dreptunghiul de arie maximă.

Date de intrare
Fișierul de intrare colturi_dr.in conține pe prima linie numărul n de linii, numărul m de coloane, iar pe următoarele linii se află cele n * m numere naturale.

Date de ieșire
Fișierul de ieșire colturi_dr.out va conține pe prima linie numerele nr, A si cnt reprezentând cele trei numere specificate în cerință.

Restricții și precizări

1 ≤ n, m ≤ 100
numărul de dreptunghiuri de extrem cu vârfuri de 1 este diferit de numărul de dreptunghiuri de extrem cu vârfuri de 0.
un dreptunghi de extrem are cel puțin două linii și două coloane

Exemplu:
colturi_dr.in

5 5
1  0  1  0  1
1  1  1  1  0
0  1  1  0  1
0  1  0  0  1
1  0  1  0  1
colturi_dr.out

11 25 9
Explicație
Sunt 9 dreptunghiuri de extrem a cărui vârfuri sunt 1, respectiv 2 ale cărui vârfuri sunt 0. Dreptunghiul de extrem de arie maximă are colțul stânga sus la (0,0) și colțul dreapta jos la (5,5).

## Cod sursă C++

```cpp
#include <iostream>
#include <fstream>
using namespace std;
ifstream fin("colturi_dr.in");
ofstream fout("colturi_dr.out");
int n, m;
int A0, A1, F0, F1;
bool a[101][101];
int p;
// complexitate O(n * (n + 1) * m / 2)
int main()
{
    fin >> n >> m;
    for(int i = 1; i <= n; ++i)
        for(int j = 1; j <= m; ++j)
           fin >> a[i][j];
    //luăm fiecare pereche de 2 linii distincte       
    for(int i = 1; i < n; ++i)
        for(int j = i + 1; j <= n; ++j)
    {
        ++p;
        int cnt1 = 0, cnt0 = 0, l, p1 = 0, p0 = 0, l1 = 0, l0 = 0;
        //căutăm prima valoarea de 1 aflată pe ambele linii
        for(l = 1; l <= m; ++l)
            if(a[i][l] == a[j][l])
               if(a[i][l] == 1)
               {
                   ++cnt1;
                   p1 = l;
                   break;
               }
               ++l;
        //căutăm toate pozițiile rămase pe care se află 1 pe ambele linii și contorizăm
        while(l <= m)
        {
            if(a[i][l] == a[j][l])
               if(a[i][l] == 1)
                   {
                       ++cnt1;
                       l1 = l;
                   }
               ++l;
        }
        //căutăm prima valoarea de 0 aflată pe ambele linii
        for(l = 1; l <= m; ++l)
            if(a[i][l] == a[j][l])
               if(a[i][l] == 0)
               {
                   ++cnt0;
                   p0 = l;
                   break;
               }
               ++l;
        //căutăm toate pozițiile rămase pe care se află 0 pe ambele linii și contorizăm
        while(l <= m)
        {
            if(a[i][l] == a[j][l])
               if(a[i][l] == 0)
                   {
                       ++cnt0;
                       l0 = l;
                   }
               ++l;
        }
        F0 += (cnt0 - 1) * cnt0 / 2; // numărul de dreptunghiuri de extrem cu vârfuri 0
        F1 += (cnt1 - 1) * cnt1 / 2; // numărul de dreptunghiuri de extrem cu vârfuri 1
        int a0, a1;
        a0 = (j - i + 1) * (l0 - p0 + 1); // aria maximă a unui dreptunghi de extrem cu vârfuri 0
        a1 = (j - i + 1) * (l1 - p1 + 1); // aria maximă a unui dreptunghi de extrem cu vârfuri 1
        A0 = max(A0, a0);
        A1 = max(A1, a1);
    }
    fout << F0 + F1 << " ";
    if(A0 > A1)
        fout << A0 << " " << F0;
    if(A0 < A1)
        fout << A1 << " " << F1;
    return 0;
}
```

## Resurse

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