# Sweep Line Geometry

Sweep Line은 좌표 평면의 이벤트를 한 방향으로 정렬해 훑으면서, 현재 선을 가로지르는 active object만 관리하는 기법입니다. 모든 쌍을 직접 비교하면 `O(N^2)`이 되는 기하 문제를 정렬과 자료구조로 줄일 때 자주 씁니다.

## 문제 신호

Sweep line은 평면 객체를 한 축 기준으로 훑을 수 있을 때 나옵니다.

| 문제 표현 | Sweep 관점 |
| --- | --- |
| 많은 직사각형의 합집합 넓이 | x 이벤트 + y 구간 cover length |
| 선분들이 교차하는지 판정 | x 이벤트 + 인접 선분만 검사 |
| 점과 구간의 포함 관계 | 이벤트 순서 + active interval |
| 거리 후보가 가까운 점만 필요 | x 순서 + y active window |
| 시간에 따라 시작/끝이 있는 객체 | 시작/끝 이벤트 |

핵심은 이벤트 사이 구간에서는 active 상태가 변하지 않는다는 점입니다.

## 이벤트 설계

직사각형 합집합 넓이를 예로 보면, 각 직사각형 `[x1, x2) x [y1, y2)`는 두 이벤트로 바뀝니다.

```text
x = x1: y 구간 [y1, y2)를 active에 추가
x = x2: y 구간 [y1, y2)를 active에서 제거
```

이벤트를 x좌표 순서로 처리하면서, 다음 이벤트 x까지의 폭과 현재 active y 길이를 곱해 넓이를 더합니다.

```text
area += coveredYLength * (nextX - currentX)
```

## 좌표 압축과 구간 의미

y좌표를 압축할 때 node가 나타내는 것은 점이 아니라 인접 좌표 사이의 구간입니다.

```text
ys = [1, 4, 10]
index 0 구간은 [1, 4)
index 1 구간은 [4, 10)
```

따라서 `[y1, y2)`를 덮으려면 압축 index `l`부터 `r - 1`까지 갱신합니다. 이 off-by-one이 직사각형 union area에서 가장 자주 틀리는 부분입니다.

## 직사각형 합집합 넓이 구현

아래 코드는 정수 좌표 직사각형들의 합집합 넓이를 계산합니다. y축 구간 cover count와 실제 덮인 길이를 Segment Tree로 관리합니다.

직사각형은 `x1<=x2`, `y1<=y2`로 정렬된 좌표를 받습니다. 좌표 차·덮인 길이·넓이 합은 long long 범위여야 합니다. 길이 0인 직사각형은 넓이에 기여하지 않습니다.

> **코드 환경: 일반 C++17 학습용.** 헤더·STL을 허용하는 로컬 예제입니다. h-contest 제출에 옮길 때는 [공통 코드](https://h.readiz.com/learn/cpp-common-library)와 문제의 공개 API에 맞춰 필요한 부분을 바꿉니다.

```cpp compile-check
#include <algorithm>
#include <vector>
using namespace std;

struct Rectangle {
    long long x1;
    long long y1;
    long long x2;
    long long y2;
};

struct Event {
    long long x;
    long long y1;
    long long y2;
    int delta;

    bool operator<(const Event& other) const {
        return x < other.x;
    }
};

struct CoverSegmentTree {
    vector<long long> ys;
    vector<int> cover;
    vector<long long> length;

    explicit CoverSegmentTree(vector<long long> coordinates)
        : ys(move(coordinates)), cover(4 * (int)ys.size(), 0), length(4 * (int)ys.size(), 0) {}

    void pull(int node, int start, int end) {
        if (cover[node] > 0) {
            length[node] = ys[end + 1] - ys[start];
        } else if (start == end) {
            length[node] = 0;
        } else {
            length[node] = length[node * 2] + length[node * 2 + 1];
        }
    }

    void update(int node, int start, int end, int left, int right, int delta) {
        if (right < start || end < left) {
            return;
        }
        if (left <= start && end <= right) {
            cover[node] += delta;
            pull(node, start, end);
            return;
        }
        int mid = (start + end) / 2;
        update(node * 2, start, mid, left, right, delta);
        update(node * 2 + 1, mid + 1, end, left, right, delta);
        pull(node, start, end);
    }

    void updateRange(long long y1, long long y2, int delta) {
        int left = (int)(lower_bound(ys.begin(), ys.end(), y1) - ys.begin());
        int right = (int)(lower_bound(ys.begin(), ys.end(), y2) - ys.begin()) - 1;
        if (left <= right) {
            update(1, 0, (int)ys.size() - 2, left, right, delta);
        }
    }

    long long coveredLength() const {
        return length[1];
    }
};

long long unionArea(const vector<Rectangle>& rectangles) {
    vector<Event> events;
    vector<long long> ys;
    for (const Rectangle& rect : rectangles) {
        if (rect.x1 == rect.x2 || rect.y1 == rect.y2) {
            continue;
        }
        events.push_back(Event{rect.x1, rect.y1, rect.y2, 1});
        events.push_back(Event{rect.x2, rect.y1, rect.y2, -1});
        ys.push_back(rect.y1);
        ys.push_back(rect.y2);
    }
    if (events.empty()) {
        return 0;
    }

    sort(events.begin(), events.end());
    sort(ys.begin(), ys.end());
    ys.erase(unique(ys.begin(), ys.end()), ys.end());

    CoverSegmentTree tree(ys);
    long long area = 0;
    long long previousX = events[0].x;

    for (int i = 0; i < (int)events.size(); ) {
        long long currentX = events[i].x;
        area += tree.coveredLength() * (currentX - previousX);

        while (i < (int)events.size() && events[i].x == currentX) {
            tree.updateRange(events[i].y1, events[i].y2, events[i].delta);
            ++i;
        }
        previousX = currentX;
    }

    return area;
}
```

좌표와 넓이 곱은 커질 수 있으므로 `long long`을 씁니다. 문제에서 모듈러 넓이를 요구하지 않는 한 중간 계산도 실제 정수 범위를 확인해야 합니다.

## 선분 교차 sweep

선분 교차 판정은 이벤트와 active set을 쓰지만 직사각형 넓이보다 구현 난도가 높습니다.

1. 각 선분의 왼쪽 끝점과 오른쪽 끝점을 이벤트로 만든다.
2. 현재 x에서 선분의 y순서를 active set에 유지한다.
3. 새 선분을 넣을 때 이웃 선분과만 교차를 검사한다.
4. 선분을 제거할 때 제거 전 이웃끼리 교차를 검사한다.

단, 같은 x좌표 이벤트, 수직 선분, 겹치는 collinear 선분까지 포함하면 comparator와 이벤트 순서가 까다롭습니다. 입문 단계에서는 직사각형 union area처럼 구간 cover가 명확한 sweep부터 익히는 것이 좋습니다.

교차하는 선분을 set에 둔 채 comparator의 x만 바꾸면 순서가 깨지므로 이벤트에서 교차·재삽입을 처리해야 합니다.

## 이벤트 순서

같은 좌표의 이벤트 처리 순서는 문제 의미에 맞춰 고정해야 합니다.

| 상황 | 처리 기준 |
| --- | --- |
| 반열린 구간 `[l, r)` | 같은 좌표에서 제거/추가 순서 영향이 적음 |
| 닫힌 구간 `[l, r]` | 끝점에서 만나는 것을 포함할지 결정 |
| 점 query와 구간 update | update 후 query인지 query 후 update인지 문제 조건 확인 |
| 선분 교차 | 시작, 수직 질의, 끝 이벤트 순서 분리 |

같은 x좌표를 한 번에 묶어 처리하면 이벤트 사이 폭이 0인 구간에서 잘못된 면적을 더하는 일을 줄일 수 있습니다.

## 시간 복잡도

| 작업 | 시간 | 메모리 |
| --- | ---: | ---: |
| 이벤트 정렬 | `O(N log N)` | `O(N)` |
| 좌표 압축 | `O(N log N)` | `O(N)` |
| 직사각형 union area | `O(N log N)` | `O(N)` |
| active set 기반 선분 sweep | `O(N log N)` + 교차 검사 | `O(N)` |

여기서 `N`은 보통 이벤트 수입니다. 직사각형 `R`개면 이벤트는 `2R`개입니다.