Bulldozer Trick (Rotating Sweep)

Bulldozer Trick, Rotating Sweep, 회전 스윕

정의

Bulldozer Trick (Rotating Sweep) 은 평면의 N 개 점에 대해 모든 두 점쌍을 잇는 직선의 기울기를 정렬 한 뒤, 기울기를 회전시키며 점들의 정렬 순서가 어떻게 바뀌는지 추적해 평면 통계를 효율적으로 푸는 기법.

핵심: 두 점이 기울기 θ 의 정렬 에서 인접 한 것은 기울기 = slope(p, q) 일 때만. 그 점쌍을 경계 사건 (event) 으로 보고 회전.

전체 사건 수 = O(N²), 각 사건이 swap 한 번 → 전체 O(N² log N) 또는 O(N²).

문제 상황과 동기

수직 sweep (x 좌표 순 정렬) 만으로는 기울기가 임의인 직선 과 관련된 문제를 풀 수 없다. 예를 들어 “세 점 삼각형의 최대 면적” 은 어느 두 점을 밑변으로 택했을 때 나머지 점 중 가장 먼 점 을 빠르게 찾아야 하는데, 이 “가장 먼 점” 의 정의가 밑변의 기울기에 따라 달라진다.

Naive 접근

모든 세 점 조합 O(N³) 시도. N=1000 이면 10⁹ 으로 불가능.

Bulldozer Trick 의 돌파구

수직 sweep 만으로 안 풀리는 평면 문제. 모든 점쌍의 기울기를 정렬 → 회전 sweep 으로 정렬 순서가 swap 되는 O(N²) 사건만 처리. 각 사건에서 segment tree 같은 자료구조로 통계를 O(log N) 갱신하면 전체 O(N² log N).

어디서 쓰이나: 최대 삼각형 면적, 사각형 카운팅, 공선 점 찾기, 임의 방향 스윕이 필요한 기하 문제. 수직 sweep만으로 안 풀리는 평면 문제. 모든 점쌍의 기울기를 정렬 → 회전 sweep으로 정렬 순서가 swap.

시각화

핵심 아이디어

모든 점쌍 (p_i, p_j) 의 기울기 θ_ij 를 정렬
초기 정렬 = θ = -∞ 에서의 정렬 (x 좌표 기준)
for each event in 기울기 순:
    swap 두 점의 정렬 순서
    이 시점에서 어떤 통계를 갱신할 수 있나?

각 swap 후, 정렬된 점들의 prefix / suffix 통계 가 한 번에 O(1) 또는 O(log N) 으로 갱신. segment tree 와 결합해 최대 삼각형 / 사각형 카운팅 같은 문제 해결.

알고리즘 세부 단계

불변량 (Invariant): order[i] 는 현재 기울기 θ 방향으로 정렬했을 때 점 i 의 순서. 각 사건 (점쌍 p, q) 에서 order[p] 와 order[q] 를 swap.

사건 정렬: 모든 O(N²) 점쌍 (i, j) 의 기울기를 정수 비교 (cross product) 로 정렬.

통계 갱신: segment tree / BIT 같은 자료구조에 점들을 order 순으로 유지하고, swap 시 두 점의 값을 교환 + 전체 최댓값 등을 조회.

예제 추적 (N=4, 점 A, B, C, D):

초기 (θ = -∞, x 좌표 순): A, B, C, D
사건 목록 (기울기 순):
  event 1: slope(A, C) = 1.5
  event 2: slope(B, D) = 2.0
  event 3: slope(A, D) = 2.5

event 1 (slope = 1.5):
  A 와 C 의 θ=1.5 방향 정렬 순서가 바뀜
  order: A <-> C swap → C, B, A, D
  (예: segment tree 에서 A 와 C 의 위치 교환, 최댓값 재계산)

event 2 (slope = 2.0):
  B 와 D swap → C, D, A, B

event 3 (slope = 2.5):
  A 와 D swap → C, A, D, B

각 swap 에서 통계 (예: 삼각형 면적 최댓값) 갱신

왜 O(N² log N) 인가: 사건 정렬 O(N² log N), 각 사건마다 segment tree 조회/갱신 O(log N), 총 O(N²) 사건.

구현

회전 sweep 골격. 모든 점쌍의 기울기 정렬 후 각 사건마다 두 점의 순서를 swap 하고 자료구조 (segment tree 등) 를 갱신.

// O(N² log N), O(N²) 메모리 (회전 스윕 + indexed 자료구조)
#include <bits/stdc++.h>
using namespace std;
using ll = long long;

struct Point {
    ll x, y;
    int id;
};

// cross product 로 기울기 비교 (정수 연산, 오차 없음)
ll cross(ll dx1, ll dy1, ll dx2, ll dy2) {
    return dx1 * dy2 - dy1 * dx2;
}

struct Event {
    int i, j; // 점쌍 인덱스
    ll dx, dy; // (j - i) 벡터

    bool operator<(const Event& o) const {
        // dy/dx 의 대소 비교 = cross product
        ll c = cross(dx, dy, o.dx, o.dy);
        if (c != 0) return c < 0; // 기울기 오름차순
        return i < o.i; // tie-break
    }
};

int main() {
    int N;
    cin >> N;
    vector<Point> pts(N);
    for (int i = 0; i < N; i++) {
        cin >> pts[i].x >> pts[i].y;
        pts[i].id = i;
    }

    // 초기 정렬: x 좌표 (θ = -∞)
    sort(pts.begin(), pts.end(), [](auto& a, auto& b) {
        return a.x < b.x || (a.x == b.x && a.y < b.y);
    });

    vector<int> order(N); // order[i] = 점 i 의 현재 순서
    vector<int> pos(N);   // pos[k] = 순서 k 에 있는 점의 id
    for (int i = 0; i < N; i++) {
        order[pts[i].id] = i;
        pos[i] = pts[i].id;
    }

    // 모든 O(N²) 점쌍의 기울기 사건 생성
    vector<Event> events;
    for (int i = 0; i < N; i++) {
        for (int j = i + 1; j < N; j++) {
            ll dx = pts[j].x - pts[i].x;
            ll dy = pts[j].y - pts[i].y;
            events.push_back({pts[i].id, pts[j].id, dx, dy});
        }
    }

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

    ll max_answer = 0; // 예: 어떤 통계의 최댓값

    // 각 사건마다 두 점을 swap 하고 통계 갱신
    for (auto& e : events) {
        int i = e.i, j = e.j;
        int pi = order[i], pj = order[j];

        // order 배열 swap
        swap(order[i], order[j]);
        swap(pos[pi], pos[pj]);

        // 여기서 segment tree / BIT 같은 자료구조로 통계 갱신
        // 예: 두 점 i, j 의 위치가 바뀌었을 때 삼각형 면적 최댓값 재계산
        // (구체적 구현은 문제 의존적)

        // max_answer = max(max_answer, query_structure());
    }

    cout << max_answer << "\n";
}

구현 팁

1. 정수 비교: 기울기 dy/dx 를 부동소수점으로 정렬하면 오차로 순서 어긋남. cross product dx1*dy2 - dy1*dx2 로 비교.
2. 수직선 처리: dx=0 인 사건은 기울기 무한대. dy 부호로 tie-break 또는 별도 처리.
3. 같은 기울기 사건: 여러 점쌍이 같은 기울기면 한 번에 처리해야 정합. 정렬 시 tie-break 규칙 명확히.
4. 자료구조 선택: segment tree (구간 최댓값, sum), BIT (누적합) 등을 점의 순서에 대해 유지.

응용

1. 최대 / 최소 삼각형 면적

세 점을 골랐을 때 면적의 max / min. 어느 두 점을 밑변 으로 정한 뒤 회전 스윕으로 나머지 점들 중 가장 먼 / 가까운 점 을 빠르게.

2. 사각형 카운팅

세 점이 한 사각형의 세 꼭짓점일 때 네 번째 점 카운팅.

3. Bulldozer 류

수직 / 수평 / 45도 외의 임의 방향 스윕 이 답을 좌우하는 문제.

4. Constellation 2 / 고압선

평면에서 공선 (collinear) 점 카운팅, 가로지르는 선분 카운팅.

복잡도

작업	비용
사건 (점쌍) 수	O(N²)
사건 정렬	O(N² log N)
사건 처리 (각 swap)	O(1) 또는 O(log N)
전체	O(N² log N)

함정

1. 같은 기울기의 사건

여러 점쌍이 같은 기울기를 가지면 한 번에 처리 해야 정합. 정렬 시 tie-break.

2. 정수 비교

기울기를 부동소수점으로 정렬하면 오차로 swap 순서가 어긋남. cross product 로 정수 비교.

3. 수직선

기울기 무한대 사건. atan2 또는 부호 변경.

4. 점이 같은 좌표

degenerate 입력 사전 제거.

BOJ 연습 문제

번호	제목	링크
BOJ 9484	최대삼각형, 최소삼각형	kokoa-lab
BOJ 16783	Bulldozer	kokoa-lab
BOJ 17973	Quadrilaterals	kokoa-lab
BOJ 17739	Constellation 2	kokoa-lab
BOJ 17625	고압선	kokoa-lab

참고

• Voronoi Diagram
• 볼록 다각형 접선 최적화
• Regions Trick