图形面积

Vijos-P1056-图形面积

实现

#include <iostream>
#include <algorithm>
#define y1 Y1
using namespace std;

typedef long long LL;
const int N = 110;
int n;
LL x1[N], y1[N]; // 左下角
LL x2[N], y2[N]; // 右上角
int a, b;
LL x[2 * N], y[2 * N];

void discrete () {
    for (int i = 1; i <= n; ++ i) {
        x[i] = x1[i];
        x[n + i] = x2[i];
    }
    sort(x + 1, x + 2 * n + 1);
    a = unique(x + 1, x + 2 * n + 1) - (x + 1);

    for (int i = 1; i <= n; ++ i) {
        y[i] = y1[i];
        y[n + i] = y2[i];
    }
    sort(y + 1, y + 2 * n + 1);
    b = unique(y + 1, y + 2 * n + 1) - (y + 1);
}

int main () {
    cin >> n;
    for (int i = 1; i <= n; ++ i)
        cin >> x1[i] >> y1[i] >> x2[i] >> y2[i];

    discrete();
    LL res = 0;
    for (int i = 2; i <= a; ++ i)
    for (int j = 2; j <= b; ++ j)
    for (int k = 1; k <= n; ++ k) {
        if (x1[k] <= x[i - 1] && x[i] <= x2[k]
            && y1[k] <= y[j - 1] && y[j] <= y2[k]
        ) {
            res += (x[i] - x[i - 1]) * (y[j] - y[j - 1]);
            break;
        }
    }
    cout << res << endl;
    return 0;
}