Cod sursa(job #2870371)

Utilizator pctirziuTirziu Petre pctirziu Data 12 martie 2022 12:00:31
Problema Invers modular Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.69 kb
#include <fstream>
#include <set>

using namespace std;
ifstream cin("colaj.in");
ofstream cout("colaj.out");
int norm[8005], norm2[8005], mat[1005][1005];
pair <int, int> puncte1[1005];
pair <int, int> puncte2[1005];
set <int> s;
set <int> s1;
int n, m;
int dir[] = {-1, 0, 0, 1};
int dir1[] = {0, -1, 1, 0};
void negre(int x, int y, int x1, int y1)
{
    int i, j;
    for(i = x; i < x1; i++)
        for(j = y; j < y1; j++)
            mat[i][j] = 1;
}
void fillx(int x, int y)
{
    int i;
    mat[x][y] = 1;
    for(i = 0; i < 4; i++){
        int xn = x + dir[i];
        int yn = y + dir1[i];
        if(!mat[xn][yn] and xn >= 1 and yn >= 1 and xn < norm[n] and yn < norm2[m])
            fillx(xn, yn);
    }
}
int main()
{
    int i, j, q;
    cin >> q >> n >> m;
    s.insert(0);
    s1.insert(0);
    s.insert(n);
    s1.insert(m);
    for(i = 1; i <= q; i++){
        cin >> puncte1[i].first >> puncte1[i].second >> puncte2[i].first >> puncte2[i].second;
        s.insert(puncte1[i].first);
        s1.insert(puncte1[i].second);
        s.insert(puncte2[i].first);
        s1.insert(puncte2[i].second);
    }
    int cnt = 1;
    for(auto it = s.begin(); it != s.end(); it++)
        norm[*it] = cnt++;
    cnt = 1;
    for(auto it = s1.begin(); it != s1.end(); it++)
        norm2[*it] = cnt++;
    for(i = 1; i <= q; i++)
        negre(norm[puncte1[i].first], norm2[puncte1[i].second], norm[puncte2[i].first], norm2[puncte2[i].second]);
    cnt = 0;
    for(i = 1; i < norm[n]; i++)
        for(j = 1; j < norm2[m]; j++)
            if(!mat[i][j]){
                cnt++;
                fillx(i, j);
            }
    cout << cnt;
    return 0;
}