13167번: 포스터

https://www.acmicpc.net/problem/13167

한 포스터가 다른 포스터를 가릴 수 있을 때, 각 포스터가 보이는 부분의 넓이를 구하는 문제이다.

포스터의 꼭지점 좌표를 압축하면 2n * 2n 격자 모양으로 만들 수 있다. 이렇게 만든 격자를 왼쪽에서부터 한 열씩 본다. 어떤 포스터의 세로 구간 내에 포스터가 붙지 않은 영역 넓이 계산 및 포스터를 붙임 체크는 Union-find 자료 구조로 빠르게 처리할 수 있다. 현재 보고 있는 열에서 가장 나중에 붙인 포스터부터 붙여 보며 각 포스터마다 보이는 영역 넓이를 누적시켜준다.

시간복잡도는 $O(n^2)$

#include<cstdio>
#include<algorithm>
using namespace std;
int n, sx[5000], sy[5000], ex[5000], ey[5000], p[10000], ix[10000], iy[10000];
long long res[5000];
int f(int x) { return x^p[x] ? p[x] = f(p[x]) : x; }
int main() {
    scanf("%d", &n);
    for (int i = 0; i < n; i++) {
        scanf("%d%d%d%d", sx + i, sy + i, ex + i, ey + i);
        ix[i] = sx[i]; ix[i + n] = ex[i];
        iy[i] = sy[i]; iy[i + n] = ey[i];
    }
    sort(ix, ix + 2 * n);
    sort(iy, iy + 2 * n);
    for (int i = 0; i < n; i++) {
        sx[i] = lower_bound(ix, ix + 2 * n, sx[i]) - ix;
        ex[i] = lower_bound(ix, ix + 2 * n, ex[i]) - ix;
        sy[i] = lower_bound(iy, iy + 2 * n, sy[i]) - iy;
        ey[i] = lower_bound(iy, iy + 2 * n, ey[i]) - iy;
    }
    for (int i = 0; i < 2 * n; i++) {
        for (int j = 0; j < 2 * n; j++) p[j] = j;
        for (int j = n; j--;) if (sx[j] <= i && i < ex[j])
            for (int k = f(sy[j]); k < ey[j]; k = p[f(k)] = f(k + 1))
                res[j] += 1LL * (ix[i + 1] - ix[i])*(iy[k + 1] - iy[k]);
    }
    for (int i = 0; i < n; i++) printf("%lld\n", res[i]);
    return 0;
}