[백준 3392] 화성지도

문제

www.acmicpc.net/problem/3392

 

알고리즘

Sweeping

 

문제

사각형을 구성하는 좌표들이 주어질 때, 모든 사각형의 면적을 구하는 문제입니다. 단 겹치는 좌표는 한 번만 계산해야 합니다.

 

각 직사각형을 두 개의 선분으로 분리한 후, x좌표를 기준으로 정렬합니다. 두개의 선분이란 직사각형을 놓았을 때 가장 왼쪽에 있는 선분, 가장 오른쪽에 있는 선분을 의미합니다. 예를 들어 직사각형을 이루는 좌표 (10,10), (20,20)을 받았다면

두 직선은 (10,10,20), (20,10,20)입니다. 앞에서부터 x좌표와 y좌표들입니다.

 

그리고 순차적으로 각 간선들을 살펴나가며 만약 왼쪽에 있는 선분이라면 그 선분이 가리키는 y좌표들을 업데이트해주고, 오른쪽에 있는 선분이라면 그 선분이 가리키는 y좌표를 다시 제거해줍니다. 왼쪽 선분은 이제부터 고려해야 하는 직사각형의 등장을 의미하고 오른쪽 선분은 해당 직사각형에 대한 고려가 끝났다는 것과 동치입니다. 이와 동시에  (현재 x좌표-이전에 처리한 x좌표)*(현재 업데이트되어있는 y좌표들의 합) 을 통해 매 순간 겹치지 않게 직사각형들을 구해나갈 수 있습니다.

 

남은 문제는 현재 업데이트 되어있는 y좌표들을 구하는 것입니다. 세그먼트 트리에서 구간 업데이트를 통해 업데이트된 y좌표들을 관리해나갈 수 있으며, 업데이트된 y좌표들의 길이를 구하기 위해 새로운 세그먼트 트리를 하나 더 사용합니다.

 

문제에서 유의할 점 중 하나는 업데이트를 할 때, y2의 좌표를 하나 감소시켜주는 것입니다. 이는 y좌표가 나타내는 것이 y~y+1까지의 구간을 나타내기 때문입니다. 시간 복잡도는 O(NlogN)입니다.

 

코드

#include <bits/stdc++.h>
#define rep(i,n) for(int i=0;i<n;++i)
#define REP(i,n) for(int i=1;i<=n;++i)
#define FAST cin.tie(NULL);cout.tie(NULL); ios::sync_with_stdio(false)
using namespace std;

typedef tuple<int, int, int, int> tp;
const int MAXN = 30000 + 2;
int N, ans;
int cnt[MAXN << 2], tree[MAXN << 2];
vector<tp> edge;

void update(int node, int nl, int nr, int ql, int qr, int val) {
    if (qr < nl || nr < ql) return;
    if (ql <= nl && nr <= qr) tree[node] += val;
    else {
        int mid = (nl + nr) / 2;
        update(node * 2, nl, mid, ql, qr, val);
        update(node * 2 + 1, mid + 1, nr, ql, qr, val);
    }
    cnt[node] = tree[node] ? nr - nl + 1 : nl ^ nr ? cnt[node * 2] + cnt[node * 2 + 1] : 0;
}

int main() {
    FAST;
    cin >> N;
    rep(i, N) {
        int a, b, c, d;
        cin >> a >> b >> c >> d;
        edge.emplace_back(a, b, d, 1);
        edge.emplace_back(c, b, d, -1);
    }
    sort(edge.begin(), edge.end());

    int prv = 0;
    rep(i, 2 * N) {
        auto [x, y1, y2, val] = edge[i];
        if (i) ans += (x - prv) * cnt[1];
        prv = x;
        update(1, 0, MAXN, y1, y2 - 1, val);
    }
    cout << ans;
    return 0;
}

 

++

40번째 줄의 의미와 구간 업데이트를 처리하지만 일반적인 세그먼트트리를 사용하는 것을 눈여겨 보도록 합시다.