# PBinfo #3483 – pct – Rezolvare C++

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

## Enunț

Cerința
Se dau n puncte distincte în plan, de coordonate întregi. Aflați numărul maxim de puncte aflate în interiorul sau pe laturile unui pătrat de latură k, având vârfurile de coordonate întregi și laturile paralele cu axele de coordonate.

Date de intrare
Fișierul de intrare pct.in conține pe prima linie numerele n și k, iar pe a doua linie n perechi de numere întregi reprezentând coordonatele punctelor, separate prin spații.

Date de ieșire
Fișierul de ieșire pct.out va conține pe prima linie numărul maxim de puncte situate în interiorul sau pe laturile unui pătrat de latură k.

Restricții și precizări

1 ≤ n ≤ 100.000
2 ≤ k ≤ 1000
coordonatele punctelor sunt cuprinse între 0 și 1000, inclusiv.

Exemplu:
pct.in

3 2
1 1
1 0
3 4
pct.out

2
Explicație
Se poate alege pătratul de latură 2, având vârful stânga-jos de coordonate (0,0).

## Cod sursă C++

```cpp
#include <fstream>
#define N 1002
using namespace std;
ifstream f("pct.in");
ofstream g("pct.out");
int n, i, j, k, nr, maxim, x, y;
int a[N][N], b[N][N], c[N];
int main()
{
    f >> n >> k;
    for(i = 1; i <= n; i++)
    {
        f >> x >> y;
        a[x+1][y+1] = 1;
    }
    for(i = 1; i <= 1001; i++)
        for(j = 1; j <= 1001; j++)
    {
        c[j] += a[i][j];
        b[i][j] = b[i][j-1] + c[j];
    }
    maxim = 0;
    for(i = 1; i <= 1001-k; i++)
        for(j = 1; j <= 1001-k; j++)
    {
        nr = b[i+k][j+k]-b[i+k][j-1]-b[i-1][j+k]+b[i-1][j-1];
        if(nr > maxim) maxim = nr;
    }
    g << maxim;
    return 0;
}
```

## Resurse

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