직사각형 스위핑.md

직사각형 합집합 면적 구하기

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

기본적으로 각 직사각형의 꼭짓점이 되는 점을 x좌표 기준으로 스위핑하면서 각 점 사이의 사각형 넓이를 구하는 식으로 답을 구한다. 위 그림과 같이 두 직사각형이 주어지면, 노랑, 빨강, 파랑에 해당하는 사각형의 넓이를 각각 구한 후 더하는 것이다. 이를 위해서

1. 우선 각 직사각형의 x 시작 좌표, x 끝 좌표와 y 시작 및 끝을 저장해놓는다. 그리고 x를 기준으로 정렬한다.
2. cnt라는 이름의 세그먼트 트리에 y 범위에 대해 x 시작 좌표에서 +1, x 끝 좌표에서 -1을 해준다.
3. cnt가 1 이상이면 (직사각형이 있는 구간이면) tree라는 이름의 세그먼트 트리에 직사각형이 있는 y 구간의 총 높이를 저장한다.
4. 각 점 사이의 x 너비와 y 구간의 총 높이(tree[1])를 곱해서 각 점 사이의 사각형 넓이를 구한다.

#include <iostream>
#include <vector>
#include <algorithm>
#define MAX 30001
using namespace std;

struct S {
    int x, y1, y2, t;
};

int tree[MAX*4], cnt[MAX*4];

void update(int x, int s, int e, int gs, int ge, int d) {
    if (e<gs||ge<s) return;
    if (gs<=s&&e<=ge) {
        cnt[x]+=d;
    } else {
        int mid=(s+e)/2;
        update(2*x, s, mid, gs, ge, d);
        update(2*x+1, mid+1, e, gs, ge, d);
    }

    if (cnt[x]>0) {
        tree[x]=e-s+1;
    } else {
        if (s==e) tree[x]=0;
        else tree[x]=tree[x*2]+tree[x*2+1];
    }
}

int main() {
    vector<S> V;
    int n;
    cin>>n;
    for (int i=0;i<n;i++) {
        int x1, y1, x2, y2;
        cin>>x1>>y1>>x2>>y2;
        V.push_back({ x1, y1, y2-1, 1 });
        V.push_back({ x2, y1, y2-1, -1 });
    }
    sort(V.begin(), V.end(), [](S &a, S &b) { return a.x < b.x; });
    int res=0;
    for (int i=0;i<V.size();i++) {
        if (i) res += (tree[1]*(V[i].x-V[i-1].x));
        update(1, 0, MAX, V[i].y1, V[i].y2, V[i].t);
    }
    cout<<res;
}

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

이 문제는 위 문제보다 좌표의 범위가 넓기 떄문에(0~10^9), 좌표를 기준으로 트리를 생성하면 메모리가 초과된다.

따라서 y의 인덱스를 기준으로 트리를 만들어 계산하면 된다. (좌표 압축)

#include <iostream>
#include <vector>
#include <algorithm>
#include <set>
#define MAX 400001
using namespace std;

struct S {
    long long x, y1, y2, t;
};

vector<long long> y;
long long seg[MAX*4];
long long cnt[MAX*4];

void update(long long x, long long s, long long e, long long gs, long long ge, long long d) {
    if (e<gs||ge<s) return;
    if (gs<=s&&e<=ge) {
        cnt[x]+=d;
    } else {
        long long mid=(s+e)/2;
        update(2*x, s, mid, gs, ge, d);
        update(2*x+1, mid+1, e, gs, ge, d);
    }

    if (cnt[x]>0) {
        seg[x]=y[e]-y[s-1];
    } else {
        if (s==e) seg[x]=0;
        else seg[x]=seg[x*2]+seg[x*2+1];
    }
}

int main() {
    set<long long> yset;
    vector<S> V;
    long long n;
    cin>>n;
    for (long long i=0;i<n;i++) {
        long long x1, y1, x2, y2;
        cin>>x1>>x2>>y1>>y2;
        yset.insert(y1); yset.insert(y2);
        V.push_back({ x1, y1, y2, 1 });
        V.push_back({ x2, y1, y2, -1 });
    }
    y.resize(yset.size());
    std::copy(yset.begin(), yset.end(), y.begin());
    sort(V.begin(), V.end(), [](S &a, S &b) { return a.x < b.x; });
    long long res=0;
    for (long long i=0;i<V.size();i++) {
        if (i) res += (seg[1]*(V[i].x-V[i-1].x));
        long long idx1 = lower_bound(y.begin(), y.end(), V[i].y1) - y.begin();
        long long idx2 = lower_bound(y.begin(), y.end(), V[i].y2) - y.begin();
        update(1, 0, MAX, idx1+1, idx2, V[i].t);
    }
    cout<<res;
}

직사각형 합집합 둘레 구하기

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

직사각형 합집합의 둘레를 구하는 문제도 비슷한 방식의 스위핑으로 해결할 수 있다.

y 구간의 총 높이를 저장하는 것은 똑같은데, 총 높이가 이전에 비해 변한만큼 둘레로 더해주면 된다.

x,y 둘레를 더해야하기 때문에 x에서 y1, y2까지, y에서 x1, x2까지를 각각 탐색하면서 값에 더해준다.

#include <iostream>
#include <vector>
#include <algorithm>
#include <string.h>
#define MAX 30001
using namespace std;

struct S {
    int x, y1, y2, t;
};

int seg[MAX*4], cnt[MAX*4];

void update(int x, int s, int e, int gs, int ge, int d) {
    if (e<gs||ge<s) return;
    if (gs<=s&&e<=ge) {
        cnt[x]+=d;
    } else {
        int mid=(s+e)/2;
        update(2*x, s, mid, gs, ge, d);
        update(2*x+1, mid+1, e, gs, ge, d);
    }

    if (cnt[x]>0) {
        seg[x]=e-s+1;
    } else {
        if (s==e) seg[x]=0;
        else seg[x]=seg[x*2]+seg[x*2+1];
    }
}

int main() {
    vector<S> V, V2;
    int n;
    cin>>n;
    for (int i=0;i<n;i++) {
        int x1, y1, x2, y2;
        cin>>x1>>y1>>x2>>y2;
        if (x2<x1) swap(x1,x2);
        if (y2<y1) swap(y1,y2);
        x1+=10000, y1+=10000, x2+=10000, y2+=10000;
        V.push_back({ x1, y1, y2-1, 1 });
        V.push_back({ x2, y1, y2-1, -1 });
        V2.push_back({ y1, x1, x2-1, 1 });
        V2.push_back({ y2, x1, x2-1, -1 });
    }
    sort(V.begin(), V.end(), [](S &a, S &b) { if (a.x==b.x) return a.t > b.t; else return a.x < b.x; });
    sort(V2.begin(), V2.end(), [](S &a, S &b) { if (a.x==b.x) return a.t > b.t; else return a.x < b.x; });

    int res=0, last=0;
    for (int i=0;i<V.size();i++) {
        update(1, 0, MAX, V[i].y1, V[i].y2, V[i].t);
        res+=abs(seg[1]-last);
        last=seg[1];
    }
    memset(seg, 0, sizeof(seg));
    last=0;
    for (int i=0;i<V2.size();i++) {
        update(1, 0, MAX, V2[i].y1, V2[i].y2, V2[i].t);
        res+=abs(seg[1]-last);
        last=seg[1];
    }
    cout<<res;
}