직전에 올린 BOJ 2389번 풀이와 99% 똑같은 풀이 방법을 가진 문제가 있다. 바로 이 문제.

BOJ 2626 - 헬기착륙장 링크
(2022.10.25 기준 D5)
(치팅 NO)

문제

2차원 정수 좌표로 표시되는 섬이 N개가 있다. 모든 섬을 포함하는 헬기 착륙장을 건설하려고 하는데 각 섬까지의 직선 거리들 중에서 최대가 되는 거리를 제일 작게 하려고 한다면, 헬기 착륙장의 위치와 그 위치로부터 가장 멀리 떨어진 섬까지의 거리를 출력

알고리즘

결국은 최소 외접원이다. 휴리스틱을 사용하자.

풀이

각 섬까지의 직선 거리들 중에서 최대가 되는 거리를 r이라고 하자. 이는 모든 섬까지의 거리를 전부 포함하는 거리가 되고, r이 최소가 되는 범위는 결국 최소 외접원이 된다.

BOJ 2389번 풀이와 똑같다.
다른 점은 N의 범위가 더 커지고, 시간 제한이 줄었고, 답을 반올림해서 출력한다는 점.

하지만 반올림하는 점이 발목을 붙잡을 것이다.
먼저 이 글을 보고 오자.
다른 언어도 그런진 모르겠는데 Python은 반올림한 결과가 0이어도 -가 붙을 수 있다.
그래서 -0.000은 예외처리해서 0.000으로 출력해주자.

코드

import sys; input = sys.stdin.readline

def ccw(a, b, c): # a-b-c가 반시계 방향인지 검사
    if (a[0] * b[1] + b[0] * c[1] + c[0] * a[1]) - (a[1] * b[0] + b[1] * c[0] + c[1] * a[0]) > 0:
        return True
    return False

def dist(a, b): # a-b 거리 계산
    return ((a[0] - b[0]) ** 2 + (a[1] - b[1]) ** 2) ** 0.5

def solve():
    N = int(input())
    points = sorted(list(map(float, input().split())) for _ in range(N)) # 오름차순 정렬

    # monotone chain
    # 볼록 껍질의 아래
    down = []
    for i in range(N):
        while len(down) > 1:
            if ccw(down[-2], down[-1], points[i]):
                break
            down.pop()
        down.append(points[i])

    # 볼록 껍질의 위
    up = []
    for i in range(N - 1, -1, -1):
        while len(up) > 1:
            if ccw(up[-2], up[-1], points[i]):
                break
            up.pop()
        up.append(points[i])

    # 위와 아래를 합쳐 볼록 껍질을 만들자.
    hull = down[:-1] + up[:-1]
    size = len(hull) # 볼록 껍질의 꼭짓점 개수

    # 중간점 구하기
    ax = ay = 0
    for x, y in hull:
        ax += x
        ay += y
    ax /= size
    ay /= size

    # 휴리스틱
    rat = 0.1 # 보정 비율
    for _ in range(5000):
        D = I = -1 # 가장 멀리 떨어진 점과의 거리 및 그 점의 인덱스
        for i in range(size):
            d = dist([ax, ay], hull[i])
            if D < d:
                D = d
                I = i

        # 가장 멀리 떨어진 점과 조금 더 가깝도록 보정
        ax += (hull[I][0] - ax) * rat
        ay += (hull[I][1] - ay) * rat
        rat *= 0.995 # 보정 비율을 줄여나간다.

    result = [format(ax, '.3f'), format(ay, '.3f'), format(max(dist([ax, ay], hull[i]) for i in range(size)), '.3f')]
    # 반올림한 결과가 -0.000이면 0.000으로 출력
    print('0.000' if result[0] == '-0.000' else result[0], '0.000' if result[1] == '-0.000' else result[1])
    print(result[2])

solve()

여담

약간 다이아 찍먹한 기분이 든다.
내가 잘해진건지 이 문제가 물다이아 문제인지 모르겠다.