백준2626 헬기착륙장

작성일 | In

문제 링크

  • http://icpc.me/2626

문제 출처

  • 2002 KOI 고등부 2번

사용 알고리즘

  • Random Shuffle
  • Gradient Descent

시간복잡도

  • $O(N)$

풀이

최소외접원(Smallest Enclosing Circle)을 구하는 문제입니다. 두 가지 풀이를 설명합니다.

랜덤으로 문제 풀기에서 소개하는 알고리즘을 사용하면 $O(N)$에 문제를 풀 수 있습니다.

어떤 점 $(x, y)$에서 가장 먼 섬까지의 거리를 $f(x, y)$라고 하면, 경사 하강법을 이용해 $f(x, y)$가 최소가 되는 지점을 찾을 수 있습니다. Epoch을 $K$로 두면 $O(NK)$에 문제를 풀 수 있습니다.

Random Shuffle을 이용한 코드는 위에 링크한 글에 있으므로 Gradient Descent를 이용한 코드만 첨부합니다.

전체 코드

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
#include <bits/stdc++.h>
using namespace std;

double x[1010], y[1010], xx, yy;

int main(){
    ios_base::sync_with_stdio(0); cin.tie(0);
    int n; cin >> n;
    for(int i=1; i<=n; i++){
        cin >> x[i] >> y[i];
        xx += x[i]; yy += y[i];
    }
    xx /= n; yy /= n;

    double alpha = 0.1;
    double r;
    for(int i=0; i<30303; i++){
        int idx = 1;
        r = 0;
        for(int j=1; j<=n; j++){
            double now = hypot(xx - x[j], yy - y[j]);
            if(now > r) r = now, idx = j;
        }
        xx += (x[idx] - xx) * alpha;
        yy += (y[idx] - yy) * alpha;
        alpha *= 0.999;
    }
    cout << fixed;
    cout.precision(3);
    if(abs(xx) < 1e-7) xx = 0;
    if(abs(yy) < 1e-7) yy = 0;
    if(abs(r) < 1e-7) r = 0;
    cout << xx << " " << yy << "\n" << r;
}