Plane Sweeping 알고리즘

- 여러 개의 직사각형이 주어졌을 때, 총 넓이를 구하는 알고리즘

- 모든 지도는 직사각형임

 

트리는 다음과 같은 방식으로 수정함

1. 직사각형의 세로선 데이터를 받아옴

2. 트리의 세로선에 해당하는 구간의 노드를 구함

3. 세로선의 종류에 따라 다음과 같이 작동 시킴

    3-1. 세로선이 시작선일 경우, 해당하는 구간의 노드의 cnt값을 1증가시킴

    3-2. 세로선이 끝선일 경우, 해당하는 구간의 노드의 cnt값을 1감소시킴

4. 해당하는 구간의 노드를 포함해 다시 루트노드까지 올라가면서 다음과 같이 작동시킴

    4-1. 위치한 노드의 cnt값이 0인 경우, 하위 두 자식 노드의 sum값을 더해 위치한 노드의 sum에 저장시킴

    4-2. 위치한 노드의 cnt값이 0보다 큰 경우, 해당하는 y축 구간 크기를 sum에 저장시킴

 

#include <stdio.h>

int N;
#define MAX_N 10000

typedef struct rec
{
    int x, y1, y2, end;
} rec;

rec make_rec(int _x, int _y1, int _y2, int _end)
{
    rec t = { _x, _y1, _y2, _end };
    return t;
}

int rec_greater_than(rec* a, rec* b)
{
    return a->x != b->x ? a->x > b->x : 0;
}

int tree[65538], cnt[65538];

void update(int x, int left, int right, int nodeLeft, int nodeRight, int val)
{
    if (left > nodeRight || right < nodeLeft)
    {
        return;
    }
    if (left <= nodeLeft && right >= nodeRight)
    {
        cnt[x] += val;
    }
    else
    {
        int mid = (nodeLeft + nodeRight) >> 1;
        update(x * 2, left, right, nodeLeft, mid, val);
        update(x * 2 + 1, left, right, mid + 1, nodeRight, val);
    }
    tree[x] = 0;
    if (cnt[x] > 0)
    {
        tree[x] = nodeRight - nodeLeft + 1;
    }
    if (cnt[x] == 0 && nodeLeft < nodeRight)
    {
        tree[x] = tree[x * 2] + tree[x * 2 + 1];
    }
}

int partition(rec a[], int l, int r)
{
    rec pivot, t;
    int i, j;
    pivot = a[l];
    i = l;
    j = r + 1;

    while (1) {
        do {
            ++i;
        } while ((!rec_greater_than(&a[i], &pivot)) && i <= r);

        do {
            --j;
        } while (rec_greater_than(&a[j], &pivot));

        if (i >= j)
        {
            break;
        }
        t = a[i];
        a[i] = a[j];
        a[j] = t;
    }
    t = a[l];
    a[l] = a[j];
    a[j] = t;
    return j;
}


void quick_sort(rec a[], int l, int r)
{
    int j;

    if (l < r)
    {
        j = partition(a, l, r);
        quick_sort(a, l, j - 1);
        quick_sort(a, j + 1, r);
    }
}

int main()
{
    freopen("input.txt", "r", stdin);
    int T;
    scanf("%d", &T);

    for (int test_case = 1; test_case <= T; test_case++)
    {
        static rec v[MAX_N * 2];
        scanf("%d", &N);

        int idx = 0, i, px, ans;
        for (i = 0; i < N; i++)
        {
            int x1, y1, x2, y2;
            scanf("%d%d%d%d", &x1, &y1, &x2, &y2);
            v[idx++] = make_rec(x1, y1, y2, 1);
            v[idx++] = make_rec(x2, y1, y2, -1);
        }

        quick_sort(v, 0, idx - 1);
        px = v[0].x;
        ans = 0;
        for (i = 0; i < idx; i++)
        {
            ans += (v[i].x - px) * tree[1];
            update(1, v[i].y1, v[i].y2 - 1, 0, 32768, v[i].end);
            px = v[i].x;
        }
        printf("#%d ", test_case);
        printf("%d\n", ans);
    }

    return 0;
}