Line Sweeping

n^2 알고리즘

Line Sweeping에는 n^2, nlogn 정도가 있다. (아래는 n^2)

x1,y1 : 왼쪽 아래 점
x2,y2 : 오른쪽 위 점

events : 첫번 째 인자 : 모든 사각형의 x1, x2저장
         두번 째 인자 : 시작 점, 끝 점 정보 저장( 시작 = 1, 끝 = -1)
         세번 째 인자 : 주어지는 사각형의 번호 저장.

ys : 모든 y1, y2저장 후 같은 값은 제거

count : ys[i]~ys[i+1]겹처진 사각형의 수

delta는 count 배열에 영향을 주는데 끝점이 나왔을 때 다음 x좌표까지 그 사각형은 포함이 되지 않는다는 뜻이므로 -1을 해주는 것이다.
반대로 시작점일 때는 포함을 한다는 뜻이므로 +1을 해준다.

ys와 events를 오름차순으로 sorting을 한다.
위 그림에서 1,2,3,4,5,6,7의 과정을 진행한다.
1번째 막대에서 보면 y1 = 2, y2 = 4가 된다. 그러면 count에는 0,1,1,0,0이 저장되는데
이말은 2~3, 3~4 까지의 길의를 포함한다는 말이다. 따라서 cutLength에는 2라는 값이
할달되고 다음 x까지의 거리와 cutLength의 값을 곱해주면 1번 막대와 2번 막대 사이의
넓이가 ret에 더해진다.
2번 막대에서 한번더 예를 들면 count에는 1,2,1,0,0이 저장되는데 1~2, 2~3, 3~4 가 포함된다는 의미이다.
다음 x좌표까지의 거리는 0이므로 ret에는 0이 더해진다.
사각형의 끝점을 지날때에는 더이상 해당 사각형의 오른쪽 변은 넓이를 계산할 때 포함이 되지않는 다는 뜻이므로 count[j] == 0이면 cutLength에 길이를 더해주지 않는다.

위와 같은 반복문이 끝나면 ret에는 위 그림의 총 넓이가 저장된다.
[-] Collapse

struct Rectangle{
    int x1, y1, x2, y2;
};
int unionArea(const vector<Rectangle>& rec){
    if (rec.empty()) return 0;
    typedef pair < int, pair<int, int> >Event;
    vector<Event> events;
    vector<int> ys;
    for (int i = 0; i < rec.size(); i++){
        ys.push_back(rec[i].y1);
        ys.push_back(rec[i].y2);
        events.push_back(Event(rec[i].x1, make_pair(1, i)));
        events.push_back(Event(rec[i].x2, make_pair(-1, i)));
    }
    sort(ys.begin(), ys.end());
    ys.erase(unique(ys.begin(), ys.end()), ys.end());
    sort(events.begin(), events.end());
    int ret = 0;
    vector<int> count(ys.size() - 1, 0);
    for (int i = 0; i < events.size(); i++) {
        int x = events[i].first, delta = events[i].second.first;
        int rectangle = events[i].second.second;
        int y1 = rec[rectangle].y1, y2 = rec[rectangle].y2;
        for (int j = 0; j < ys.size(); j++){
            if (y1 <= ys[j] && ys[j] < y2)
                count[j] += delta;
        }
        int cutLength = 0;
        for (int j = 0; j < ys.size() - 1; j++){
            if (count[j] > 0)
                cutLength += ys[j + 1] - ys[j];
        }
        if (i + 1 < events.size())
            ret += cutLength * (events[i + 1].first - x);
    }
    return ret;
}