[도전 29일차] 헬기 착륙장 - KOI 고등부 풀이

※복습 : 

문제 : 백준 2626 헬기 착륙장

문제 링크

 

사용 알고리즘 :  기하 - 최소 외접원

 

풀이 : 

이 문제는 '주어진 모든 점을 포함하는 최소 외접원 찾기'로 요약 가능하다.

(ho94949님의 글, 최소 외접원 찾기에 정말 자세한 내용이 있다.)

 

외접원의 중심을 찾는 과정은 거리 함수 $$z={\sqrt (x^2+y^2)}$$가 볼록함수라는 것으로부터 출발한다.

 

구글에 z=sqrt(x^2+y^2) 를 검색

위 그래프의 꼭짓점을 우리가 원하는 외접원의 중심 (Ax,Ay) 라고 하자.

임의의 점을 하나 잡고, (Ax,Ay)에 가깝게 가는 과정을 반복할 수 있다면 어떨까? 최종적으로는 Ax,Ay에 도착할 수 있을 것이다.

 

그렇다면 (Ax,Ay)에 가까운지는 어떻게 판단할까? 

(Ax,Ay)는 가장 거리가 먼 점과의 거리가 최소인 점이므로, 

현재 내 위치에서 각 점 간의 거리를 계산한 후에, 가장 먼 점과 가까워지는 방향으로 이동하면 된다. (가장 먼 점과 거리가 감소한다 -> 거리의 최댓값이 감소한다 -> Ax,Ay와 가까워진다.) 

이때 너무 많이 이동해버리면 (Ax,Ay)를 기준으로 진동하는 사태가 발생할 수도 있다. 그렇기 때문에 이 과정이 반복될 수록 이동하는 비율을 감소시켜주면, Ax,Ay에 계속 가깝게 갈 수 있다.

 

이런 방법을 휴리스틱이라 한다. 처음 접한 분야인데, Guesstimation과 비슷한 어림짐작 기법으로 보인다.

 

코드 중간에 보면 0.995, 0.1 이런 숫자들이 보이는데 어떻게 정하는지는 나도 잘 모르겠다.. 더 탐구가 필요하다.

코드

#include<stdio.h>
#include<math.h>
int n;
struct Point{
    double x,y;
    Point():x(0.0),y(0.0){}
}arr[1010];
void input(){
    scanf("%d",&n);
    int x,y;
    for(int i=0;i<n;i++){
        scanf("%d%d",&x,&y);
        arr[i].x=(double)x; arr[i].y=(double)y;
    }
}
void solve(){
    auto norm = [](double x,double y){
        return x*x+y*y;
    };
    Point avg;
    for(int i=0;i<n;i++){
        avg.x+=arr[i].x; avg.y+=arr[i].y;
    }
    avg.x*=1.0/n; avg.y*=1.0/n;
    double ans=1e10,px=avg.x,py=avg.y,w=0.1;
    int cnt=10000;
    while(cnt--){
        double max_v=0,tmp_v;
        int max_id; 
        for(int i=0;i<n;i++){
            tmp_v=norm(px-arr[i].x,py-arr[i].y);
            if(tmp_v>max_v){
                max_v=tmp_v;
                max_id=i;
            }
        }
        if(max_v<ans)
            ans=max_v;
        px+=(arr[max_id].x-px)*w;
        py+=(arr[max_id].y-py)*w;
        w*=0.995;
    }
    printf("%.3lf %.3lf\n%.3lf",px,py,sqrt(ans));
}
int main(){
    input();
    solve();
}

이 외에도 다양한 풀이가 있다. KOI 공식 풀이에서는 '보로노이 다이어그램', 'Convex Hull 위에 있는 세 점의 외접원 탐색' 등의 방법을 제시한다.

 

궁금한 점이 있으시다면 질문 남겨주세요 :)