[Algorithm] cpp-python 백준 12771번: Oil

문제

링크: https://www.acmicpc.net/problem/12771
요약: 수평 선분(유전)을 한 번의 직선 시추선이 지나가며 만나는 모든 선분의 길이 합을 최대로 하라. 선분 끝점에 스치기만 해도 채취 가능하며, 서로 다른 선분들은 서로 만나지 않는다.

제한/스펙

n ≤ 2000, 각 선분 좌표 |x| ≤ 1e6, y ∈ [1, 1e6]
시간 제한 10초, 메모리 512MB
어떤 두 선분도 서로 교차하거나 닿지 않음(같은 y여도 x구간이 겹치지 않음)

입력/출력 예시

접근 개요

선분 i의 양 끝점(앵커)에서 출발하는 모든 직선의 기울기 k를 고려하면, 다른 선분 j가 포함되기 위한 k의 범위가 닫힌 구간 [k_lo, k_hi]로 표현된다.
각 j에 대해 이 구간을 이벤트(시작, 끝)로 추가하고, k 축에서 시작 이벤트를 먼저 처리하는 스위프를 수행하면 해당 k에서 포함되는 선분 길이 합을 빠르게 갱신할 수 있다.
선분 끝점에 스쳐도 포함되므로 양 끝 이벤트는 모두 “포함(닫힌 구간)“으로 처리해야 한다. 기준 선분 i의 길이는 항상 포함(베이스 가중치).

알고리즘 설계

상태/전이
- 기준: 각 선분 i의 좌/우 끝점 (총 2n개의 앵커)을 모두 시도
- 다른 선분 j(≠i)에 대해 dy = y_j - y_i
  - dy = 0이면 교차 불가(문제 보장상 겹치지도 않음) → 스킵
  - k가 만족해야 할 범위: (x_jL - x_iA)/dy ≤ k ≤ (x_jR - x_iA)/dy (dy의 부호에 따라 자동 정렬되도록 lo/hi를 취함)
- 이벤트: (k, type, weight) where type ∈ {start, end}, weight = 선분 j의 길이
- 정렬: k 오름차순, 동일 k에서는 start 먼저 → 닫힌 구간 보장
절차
1. i와 앵커 선택 → base = width(i)
2. 모든 j에 대해 [k_lo, k_hi] 이벤트를 수집하고 정렬
3. 스위프: start에서 더하고(best 갱신), 같은 k의 end는 그 다음에 빼기
4. 모든 앵커에 대해 최대값 갱신 → 전역 최댓값 출력
올바름 근거(스케치)
- 각 j의 포함 여부는 직선의 기울기 k에 대한 닫힌 범위로 정확히 기술된다(교차 혹은 끝점 접촉 포함).
- 동일 k에서 start를 end보다 먼저 처리하면 경계에서도 포함이 유지되어 닫힌 구간을 충실히 반영한다.
- 모든 앵커(양 끝점)를 시도함으로써, 최적 직선이 어떤 선분의 내부를 지나는 경우도 적어도 한 끝점을 통과하는 동등 기울기 집합으로 재현 가능하다.

복잡도

한 앵커에서 이벤트는 O(n), 정렬 O(n log n) → 앵커 2n개로 O(n^2 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
// 더 많은 정보는 42jerrykim.github.io 에서 확인하세요.
#include <bits/stdc++.h>
using namespace std;

struct Segment {
    long long leftX;
    long long rightX;
    long long y;
    long long width;
};

struct Event {
    long double value;   // slope k
    int type;            // 0 = start (inclusive), 1 = end (inclusive)
    long long weight;    // segment width
};

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 x0, x1, y;
        cin >> x0 >> x1 >> y;
        long long l = min(x0, x1);
        long long r = max(x0, x1);
        segs[i] = {l, r, y, r - l};
    }

    long long best = 0;
    for (int i = 0; i < n; ++i) {
        // Try both endpoints of segment i as the anchor point the line must pass through
        for (int endpoint = 0; endpoint < 2; ++endpoint) {
            long long anchorX = (endpoint == 0 ? segs[i].leftX : segs[i].rightX);
            long long anchorY = segs[i].y;

            vector<Event> events;
            events.reserve(2 * (n - 1));

            long long base = segs[i].width; // the line always intersects segment i at the anchor point

            for (int j = 0; j < n; ++j) {
                if (j == i) continue;
                long long dy = segs[j].y - anchorY;
                if (dy == 0) {
                    // Same y-level as anchor: cannot be hit due to non-overlap guarantee
                    continue;
                }
                // k in [ (leftX - anchorX)/dy , (rightX - anchorX)/dy ]
                long double k1 = (long double)(segs[j].leftX  - anchorX) / (long double)dy;
                long double k2 = (long double)(segs[j].rightX - anchorX) / (long double)dy;
                long double lo = min(k1, k2);
                long double hi = max(k1, k2);
                events.push_back({lo, 0, segs[j].width}); // start inclusive
                events.push_back({hi, 1, segs[j].width}); // end inclusive
            }

            sort(events.begin(), events.end(), [](const Event& a, const Event& b) {
                if (a.value != b.value) return a.value < b.value;
                return a.type < b.type; // start(0) before end(1)
            });

            long long current = base;
            best = max(best, current);

            for (size_t idx = 0; idx < events.size();) {
                long double v = events[idx].value;
                while (idx < events.size() && events[idx].value == v && events[idx].type == 0) {
                    current += events[idx].weight;
                    ++idx;
                }
                best = max(best, current);
                while (idx < events.size() && events[idx].value == v && events[idx].type == 1) {
                    current -= events[idx].weight;
                    ++idx;
                }
            }
        }
    }

    cout << best << "\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
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
# 더 많은 정보는 42jerrykim.github.io 에서 확인하세요.
import sys
from fractions import Fraction

input = sys.stdin.readline

def solve():
    n_line = input().strip()
    if not n_line:
        return
    n = int(n_line)
    segs = []
    for _ in range(n):
        x0, x1, y = map(int, input().split())
        l, r = (x0, x1) if x0 <= x1 else (x1, x0)
        segs.append((l, r, y, r - l))

    best = 0
    for i in range(n):
        for endpoint in range(2):
            anchorX = segs[i][0] if endpoint == 0 else segs[i][1]
            anchorY = segs[i][2]
            base = segs[i][3]

            events = []  # (k: Fraction, type: 0 start / 1 end, weight)
            for j in range(n):
                if j == i:
                    continue
                dy = segs[j][2] - anchorY
                if dy == 0:
                    continue
                k1 = Fraction(segs[j][0] - anchorX, dy)
                k2 = Fraction(segs[j][1] - anchorX, dy)
                lo, hi = (k1, k2) if k1 <= k2 else (k2, k1)
                events.append((lo, 0, segs[j][3]))
                events.append((hi, 1, segs[j][3]))

            events.sort(key=lambda e: (e[0], e[1]))  # start(0) before end(1)

            cur = base
            if cur > best:
                best = cur
            idx = 0
            m = len(events)
            while idx < m:
                v = events[idx][0]
                while idx < m and events[idx][0] == v and events[idx][1] == 0:
                    cur += events[idx][2]
                    idx += 1
                if cur > best:
                    best = cur
                while idx < m and events[idx][0] == v and events[idx][1] == 1:
                    cur -= events[idx][2]
                    idx += 1

    print(best)

if __name__ == "__main__":
    solve()