[Algorithm] C++ 백준 13310번: 먼 별

1
2
3
4
5
6
7
8
9

입력:
3 10
0 0 1 0
10 0 -1 0
5 5 0 0

출력:
5
50

1
2
3
4
5
6

1. 시간 범위 [0, T]에서 삼분 탐색
2. 각 시간 t에 대해:
   a) 모든 별의 위치 계산: (x + dx*t, y + dy*t)
   b) Andrew's Monotone Chain으로 Convex Hull 구성
   c) Rotating Calipers로 Hull의 지름 계산
3. 최소 거리를 갖는 시간과 거리의 제곱 출력

1
2
3
4
5

1. 점들을 x좌표 기준으로 정렬 (동일하면 y좌표)
2. 아래쪽 껍질(Lower Hull) 구성: 좌에서 우로
   - 최근 두 점과 새 점의 외적이 반시계방향이 될 때까지 제거
3. 위쪽 껍질(Upper Hull) 구성: 우에서 좌로
4. 두 껍질 결합

1
2
3
4
5

각 가장자리 (i, i+1)에 대해:
- 그 가장자리에 수직인 방향으로 가장 먼 점 j 찾기
- 양쪽 끝점까지 거리 계산
- 전체 최대값 갱신
(반복 조건으로 j는 항상 전진 → O(n))

1
2
3
4
5
6

시간 범위 [lo, hi] 중에서:
- m1 = lo + (hi-lo)/3
- m2 = hi - (hi-lo)/3
- if dist(m1) > dist(m2): lo = m1 (우측에 최소값)
  else: hi = m2 (좌측에 최소값)
- 범위가 충분히 좁아질 때까지 반복

  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
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155

// 더 많은 정보는 42jerrykim.github.io 에서 확인하세요.
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;

struct Point {
    ll x, y;
    ll dx, dy;
};

int N;
ll T;
vector<Point> stars;

// 외적: (A-O) × (B-O)
ll cross(ll ax, ll ay, ll bx, ll by) {
    return ax * by - ay * bx;
}

ll cross(const Point& O, const Point& A, const Point& B) {
    return cross(A.x - O.x, A.y - O.y, B.x - O.x, B.y - O.y);
}

// 두 점 사이의 거리의 제곱
ll dist2(const Point& A, const Point& B) {
    return (A.x - B.x) * (A.x - B.x) + (A.y - B.y) * (A.y - B.y);
}

// 시간 t에서 모든 별의 위치 계산
vector<Point> getPositions(ll t) {
    vector<Point> pts(N);
    for (int i = 0; i < N; i++) {
        pts[i].x = stars[i].x + stars[i].dx * t;
        pts[i].y = stars[i].y + stars[i].dy * t;
    }
    return pts;
}

// Andrew's Monotone Chain 알고리즘으로 Convex Hull 구성
vector<Point> convexHull(vector<Point>& pts) {
    int n = pts.size();
    if (n < 3) return pts;
    
    sort(pts.begin(), pts.end(), [](const Point& a, const Point& b) {
        if (a.x != b.x) return a.x < b.x;
        return a.y < b.y;
    });
    
    vector<Point> hull;
    
    // 아래쪽 껍질 (Lower hull)
    for (int i = 0; i < n; i++) {
        while (hull.size() >= 2 && cross(hull[hull.size()-2], hull[hull.size()-1], pts[i]) <= 0)
            hull.pop_back();
        hull.push_back(pts[i]);
    }
    
    // 위쪽 껍질 (Upper hull)
    int lower_size = hull.size();
    for (int i = n - 2; i >= 0; i--) {
        while (hull.size() > lower_size && cross(hull[hull.size()-2], hull[hull.size()-1], pts[i]) <= 0)
            hull.pop_back();
        hull.push_back(pts[i]);
    }
    
    hull.pop_back(); // 중복 제거
    return hull;
}

// Rotating Calipers로 Convex Hull의 지름(최대 거리) 계산
ll rotatingCalipers(vector<Point>& hull) {
    int n = hull.size();
    if (n == 1) return 0;
    if (n == 2) return dist2(hull[0], hull[1]);
    
    ll maxDist = 0;
    int j = 1;
    
    for (int i = 0; i < n; i++) {
        int ni = (i + 1) % n;
        ll ex = hull[ni].x - hull[i].x;
        ll ey = hull[ni].y - hull[i].y;
        
        // j가 가장자리 (i, ni)로부터 가장 먼 점이 되도록 이동
        while (true) {
            int nj = (j + 1) % n;
            ll v1x = hull[j].x - hull[i].x;
            ll v1y = hull[j].y - hull[i].y;
            ll v2x = hull[nj].x - hull[i].x;
            ll v2y = hull[nj].y - hull[i].y;
            
            // nj가 더 먼지 확인 (외적으로 판단)
            if (cross(ex, ey, v2x - v1x, v2y - v1y) > 0) {
                j = nj;
            } else {
                break;
            }
        }
        
        maxDist = max(maxDist, dist2(hull[i], hull[j]));
        maxDist = max(maxDist, dist2(hull[ni], hull[j]));
    }
    
    return maxDist;
}

// 시간 t에서 최대 거리 계산
ll calc(ll t) {
    vector<Point> pts = getPositions(t);
    vector<Point> hull = convexHull(pts);
    return rotatingCalipers(hull);
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    
    cin >> N >> T;
    stars.resize(N);
    
    for (int i = 0; i < N; i++) {
        cin >> stars[i].x >> stars[i].y >> stars[i].dx >> stars[i].dy;
    }
    
    // 삼분 탐색으로 최소값 찾기
    ll lo = 0, hi = T;
    
    while (lo + 2 < hi) {
        ll m1 = lo + (hi - lo) / 3;
        ll m2 = hi - (hi - lo) / 3;
        
        if (calc(m1) > calc(m2)) {
            lo = m1;
        } else {
            hi = m2;
        }
    }
    
    // 남은 후보들 중 최소 선택
    ll ansTime = lo;
    ll ansDist = calc(lo);
    
    for (ll t = lo + 1; t <= hi; t++) {
        ll d = calc(t);
        if (d < ansDist) {
            ansDist = d;
            ansTime = t;
        }
    }
    
    cout << ansTime << "\n" << ansDist << "\n";
    
    return 0;
}