[BOJ 3392] 화성 지도

[BOJ 3392]화성 지도 - P2

문제 설명

N개의 직사각형 좌표(왼쪽 아래, 오른쪽 위)가 주어진다. N개의 직사각형을 모두 겹쳤을 때 총 넓이를 구해야한다.

문제 풀이

직사각형의 좌표값을 입력받을 때, 왼쪽 아래 좌표는 해당 직사각형이 차지하는 y좌표의 불을 켜는 것이고 오른쪽 위 좌표는 불을 끄는 행위라고 생각해보자. 우선 라인스위핑으로 접근하기 위해서 x좌표 오름차순으로 정렬한다. 정렬하고 나면 왼쪽 -> 오른쪽의 순서로 좌표를 살펴보게 되므로 현재넓이는 (현재 x좌표 값 - 지난 x좌표 값) * (높이의 총합) 으로 구할 수 있고, 이 값들을 모두 더하면 전체 넓이를 구할 수 있다.

그러면 이제 '넓이의 총합'을 구하기만 하면 된다. 넓이의 총합은 좌표의 범위에 해당하는 0 ~ 30000 까지 불이 켜져 있는 값이 모두 몇 개인지 세면 된다. 매번 0 ~ 30000을 세어보면 시간이 $O(N^{2})$가 되므로 초과된다. 이때 lazy propagation 의 아이디어를 차용해서 풀어볼 수 있다. [l,r] 범위 안에 모두 불이 켜져 있다면 해당 범위를 커버하는 segment tree의 값을 1 증가시키면 된다. 따라서 0 ~ 30000까지 직사각형 높이의 총 합은 루트노드인 len[1]배열만 찾아보면 된다.

 

소스 코드

#include<stdio.h>
#include<algorithm>
#include<vector>
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;

const int SIZE = 30009;
#define START 1
#define END -1
vector<pair<pii,pii>> v;
int len[SIZE*8],cnt[SIZE*8];
int n,startIdx=1;

void update(int node,int cl,int cr,int ql,int qr,int diff){
    if(cl > qr || ql > cr) return;
    if(qr >= cr && ql <= cl) cnt[node] += diff;

    else{
        int mid = (cl+cr)/2;
        update(node*2,cl,mid,ql,qr,diff);
        update(node*2+1,mid+1,cr,ql,qr,diff);
    }

    if(cnt[node] >= 1) len[node] = cr - cl + 1;
    else{
        len[node] = len[node*2] + len[node*2+1];
    }

}

int main(){
    scanf("%d",&n);
    for(;startIdx < 30000 ; startIdx *= 2);

    for(int i=1  ; i<=n ; i++){
        int x1,y1,x2,y2;    scanf("%d %d %d %d",&x1,&y1,&x2,&y2);
        v.push_back({{x1,y1},{y2-y1, START}});
        v.push_back({{x2,y1},{y2-y1, END}});
    }

    sort(v.begin(), v.end());

    ll ans = 0;
    int lastX = 0;
    for(int i=0 ; i<v.size() ; i++){
        int curX = v[i].first.first,curY = v[i].first.second,h = v[i].second.first,diff = v[i].second.second;

        if(i > 0){
            ll curArea = (curX - lastX) * 1LL * len[1];
            ans += curArea;
        }

        update(1,1,startIdx,curY+1,curY + h - 1 + 1,diff); // 0 base
        lastX = curX;
    }

    printf("%lld\n",ans);   

    return 0;
}