[Algorithm] cpp-python 백준 9244번: 핀볼

문제

링크: https://www.acmicpc.net/problem/9244
요약: 무한히 높은 곳에서 x = x0 지점에 공을 떨어뜨리면, 공은 수직으로 내려오다 선분을 만나면 그 선분을 아래쪽으로 따라 흐른다. 더 낮은 끝점에 도달하면 다시 수직 낙하한다. 최종적으로 공이 멈추는 x좌표를 구하라.
제한: N ≤ 100,000, |x|, |y| ≤ 1,000,000. 선분은 서로 교차하지 않고, 수직/수평선은 없다. 끝점도 선분에 포함된다.

입력/출력

1
2
3
4
5
입력
N
x1 y1 x2 y2
... (총 N줄)
x0

1
2
출력
공의 최종 위치 x좌표

예제 1

1
2

예제 2

1
0

접근 개요

선분이 서로 교차하지 않으므로 임의의 x에서 위→아래 순서는 이벤트 사이 구간에서 변하지 않는다.
x를 왼쪽→오른쪽으로 스캔하며 활성 선분 집합을 현재 x에서의 y순(아래→위)으로 유지한다.
각 선분의 더 낮은 끝점 x=low_x에서, 그 시점 활성 집합에서 “해당 선분 바로 아래”를 찾으면 흘러내림 그래프의 간선을 얻는다.
시작 x0에서 활성 집합의 맨 위 선분을 찾고, 간선을 따라 아래로 이동하면 최종 x좌표에 도달한다.

flowchart TD
    A[x0에서 낙하] -->|첫 교차| S1[선분 S1]
    S1 -->|하단(low_x)| S2[선분 S2]
    S2 -->|하단(low_x)| S3[선분 S3]
    S3 --> G[지면: 더 아래 선분 없음]
    G -->|정답| X[최종 x좌표]

알고리즘

이벤트 정의:
- 좌끝 x=xl: 활성 집합에 삽입
- 하단 x=low_x: 현재 집합에서 바로 아래 선분을 찾고 nxt[i]로 기록(없으면 -1)
- 우끝 x=xr: 활성 집합에서 제거
- 시작 x=x0: 현재 집합의 최상단 선분을 시작점으로 기록
비교 함수: y(x) 비교를 부동소수점 없이 정수 교차곱(__int128)으로 수행해 오차를 제거.
활성 집합: std::set<int, Comparator>로 유지. 현재 x가 바뀔 때마다 비교 기준에 반영되도록 캡처 포인터 사용.
시작에서 nxt를 따라가 마지막 선분의 더 낮은 끝점 x가 정답. 시작 시 활성 집합이 비어 있으면 정답은 x0.

정당성 요약:

교차가 없으므로 이벤트 사이 구간에서 선분의 상하 순서가 보존된다.
하단점에서 바로 아래 선분으로만 흘러갈 수 있으므로, low_x 시점의 바로 아래 탐색이 정확하다.
따라서 단 한 번의 스위프로 구성한 nxt를 따라가면 실제 물리 흐름과 일치한다.

복잡도

이벤트 수 O(N). 각 이벤트 처리 O(log N). 전체 O(N log N), 메모리 O(N).

구현 (C++)

  1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
// 더 많은 정보는 42jerrykim.github.io 에서 확인하세요.
#include <bits/stdc++.h>
using namespace std;

struct Segment {
    long long xl, yl, xr, yr; // xl < xr
    long long low_x, low_y;   // lower endpoint
};

struct Event {
    long long x;
    int type; // 0=insert, 1=lowpoint, 2=startQuery, 3=remove
    int id;   // segment id or -1 for startQuery
    bool operator<(const Event& other) const {
        if (x != other.x) return x < other.x;
        return type < other.type; // insert -> lowpoint -> start -> remove
    }
};

struct Comparator {
    const vector<Segment>* segs;
    const long long* currX;
    bool operator()(int a, int b) const {
        if (a == b) return false;
        const Segment& A = (*segs)[a];
        const Segment& B = (*segs)[b];
        long long x = *currX;

        __int128 dxA = (__int128)(A.xr - A.xl);
        __int128 dyA = (__int128)(A.yr - A.yl);
        __int128 dxB = (__int128)(B.xr - B.xl);
        __int128 dyB = (__int128)(B.yr - B.yl);

        // Compare y_A(x) ? y_B(x) without division:
        // y_A(x) = yl_A + dyA/dxA * (x - xl_A)
        // Compare (yl_A*dxA + dyA*(x - xl_A)) / dxA vs (yl_B*dxB + dyB*(x - xl_B)) / dxB
        __int128 valA = (__int128)A.yl * dxA + dyA * (__int128)(x - A.xl); // y(x)*dxA
        __int128 valB = (__int128)B.yl * dxB + dyB * (__int128)(x - B.xl); // y(x)*dxB

        __int128 left = valA * dxB;
        __int128 right = valB * dxA;

        if (left != right) return left < right; // ascending by y
        return a < b; // tie-break by id for stability
    }
};

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int N;
    if (!(cin >> N)) return 0;
    vector<Segment> segs(N);
    for (int i = 0; i < N; ++i) {
        long long x1, y1, x2, y2;
        cin >> x1 >> y1 >> x2 >> y2;
        if (x1 < x2) {
            segs[i].xl = x1; segs[i].yl = y1;
            segs[i].xr = x2; segs[i].yr = y2;
        } else {
            segs[i].xl = x2; segs[i].yl = y2;
            segs[i].xr = x1; segs[i].yr = y1;
        }
        if (segs[i].yl <= segs[i].yr) {
            segs[i].low_x = segs[i].xl;
            segs[i].low_y = segs[i].yl;
        } else {
            segs[i].low_x = segs[i].xr;
            segs[i].low_y = segs[i].yr;
        }
    }
    long long x0;
    cin >> x0;

    vector<Event> events;
    events.reserve(3LL * N + 1);
    for (int i = 0; i < N; ++i) {
        events.push_back({segs[i].xl, 0, i});      // insert at left
        events.push_back({segs[i].low_x, 1, i});   // lowpoint query
        events.push_back({segs[i].xr, 3, i});      // remove at right
    }
    events.push_back({x0, 2, -1});                 // start query
    sort(events.begin(), events.end());

    long long currX = 0;
    Comparator comp{&segs, &currX};
    std::set<int, Comparator> active(comp);

    vector<int> nxt(N, -1);
    int startSeg = -1;
    bool startDone = false;

    for (const auto& ev : events) {
        currX = ev.x;

        if (ev.type == 0) {
            active.insert(ev.id);
        } else if (ev.type == 1) {
            int i = ev.id;
            auto it = active.find(i);
            if (it != active.end()) {
                if (it == active.begin()) {
                    nxt[i] = -1;
                } else {
                    auto pit = prev(it);
                    nxt[i] = *pit;
                }
            } else {
                nxt[i] = -1; // safety guard
            }
        } else if (ev.type == 2) {
            if (!startDone) {
                if (active.empty()) {
                    startSeg = -1;
                } else {
                    auto it = active.end();
                    --it;
                    startSeg = *it; // topmost y at x0
                }
                startDone = true;
            }
        } else { // remove
            int i = ev.id;
            auto it = active.find(i);
            if (it != active.end()) active.erase(it);
        }
    }

    if (startSeg == -1) {
        cout << x0 << '\n';
        return 0;
    }
    int s = startSeg;
    while (nxt[s] != -1) s = nxt[s];
    cout << segs[s].low_x << '\n';
    return 0;
}

구현 (Python)

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
# 더 많은 정보는 42jerrykim.github.io 에서 확인하세요.
# 참고: 본 문제의 핵심은 "현재 x에 의존하는 순서"를 유지하는 균형 BST가 필요합니다.
# 파이썬 표준 라이브러리만으로는 비교자가 동적으로 변하는 정렬 집합을 직접 제공하지 않으므로
# 실전 제출은 C++ 권장입니다. 아래는 로직 스켈레톤입니다.

import sys
input = sys.stdin.readline

def solve():
    N = int(input())
    segs = []
    for _ in range(N):
        x1, y1, x2, y2 = map(int, input().split())
        if x1 < x2:
            xl, yl, xr, yr = x1, y1, x2, y2
        else:
            xl, yl, xr, yr = x2, y2, x1, y1
        low_x, low_y = (xl, yl) if yl <= yr else (xr, yr)
        segs.append((xl, yl, xr, yr, low_x, low_y))
    x0 = int(input())

    # 이벤트 생성: (x, type, id) — type: 0 insert, 1 lowpoint, 2 start, 3 remove
    events = []
    for i, (xl, yl, xr, yr, low_x, low_y) in enumerate(segs):
        events.append((xl, 0, i))
        events.append((low_x, 1, i))
        events.append((xr, 3, i))
    events.append((x0, 2, -1))
    events.sort()

    # 실제 제출은 C++ 구현 권장.
    # 여기서는 알고리즘 개요만 유지합니다.
    print(x0)

if __name__ == "__main__":
    solve()