Cod sursa(job #1988705)

Utilizator EuAlexOtaku Hikikomori EuAlex Data 4 iunie 2017 13:26:17
Problema Reuniune Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.23 kb
#include <fstream>
#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

struct DREPT {
    int x1, x2, y1, y2;
};

vector <int> vx, vy;
vector <DREPT> v;
int a[10][10];
int dx[] = {-1, 0, 1, 0},
    dy[] = {0, 1, 0, -1};

/// Raspunsuri
long long arie, perm;

bool acoperit(int x1, int y1, int x2, int y2) {
    for(int i = 0; i < 3; ++ i) {
        if(v[i].x1 <= x1 && x2 <= v[i].x2 && v[i].y1 <= y1 && y2 <= v[i].y2) {
            return 1;
        }
    }
    return 0;
}

void fillu(int x, int y) {
    a[x][y] = 2;
    arie += 1LL * (vx[x] - vx[x - 1]) * (vy[y] - vy[y - 1]);
    for(int k = 0; k < 4; ++ k) {
        int new_x, new_y;
        new_x = x + dx[k];
        new_y = y + dy[k];
        if(a[new_x][new_y] == 1) {
            fillu(new_x, new_y);
        }
    }
}

void margine(int x, int y) {
    for(int k = 0; k < 4; ++ k) {
        int new_x, new_y;
        new_x = x + dx[k];
        new_y = y + dy[k];
        if(a[new_x][new_y] == 0) {
            if(k % 2 == 0) {
                perm += (vy[y] - vy[y - 1]);
            } else {
                perm += (vx[x] - vx[x - 1]);
            }
        }
    }
}

int main() {
    ifstream fin("reuniune.in");
    ofstream fout("reuniune.out");

    for(int i = 0; i < 3; ++ i) {
        int x1, x2, y1, y2;
        fin >> x1 >> y1 >> x2 >> y2;
        vx.push_back(x1);
        vx.push_back(x2);
        vy.push_back(y1);
        vy.push_back(y2);
        v.push_back({x1, x2, y1, y2});
    }

    sort(vx.begin(), vx.end());
    sort(vy.begin(), vy.end());

    for(int i = 1; i < vx.size(); ++ i) {
        for(int j = 1; j < vy.size(); ++ j) {
            if(acoperit(vx[i - 1], vy[j - 1], vx[i], vy[j])) {
                a[i][j] = 1;
            }
        }
    }

    for(int i = 1; i < vx.size(); ++ i) {
        for(int j = 1; j < vy.size(); ++ j) {
            if(a[i][j] == 1) {
                fillu(i, j);
            }
        }
    }

    for(int i = 1; i < vx.size(); ++ i) {
        for(int j = 1; j < vy.size(); ++ j) {
            if(a[i][j] == 2) {
                margine(i, j);
            }
        }
    }

    fout << arie << " " << perm;

    return 0;
}