[BOJ 4225] 쓰레기 슈트

문제

---

https://www.acmicpc.net/problem/4225

풀이

---

볼록 껍질을 구한 뒤, 각 변에 대해 꼭짓점과의 거리의 최댓값을 구해준다.

그중 최솟값이 정답이 된다.

처음엔 볼록 껍질을 구하지 않고 풀려 했지만, 오목 다각형의 무궁무진한 반례 때문에 실패했다.

그리고 꼭짓점 순서대로 입력된 점을 이용해서 볼록 껍질을 구하려 했지만 시계 방향으로 주어졌는지 반시계 방향으로 주어졌는지 판단하기가 어려워서 실패했다.

코드

---

import sys
from math import ceil


def tangent(x, y):
    if x == a:
        return 1, y
    if x > a:
        return 0, (y - b) / (x - a), x
    if x < a:
        return 2, (y - b) / (x - a), x


def ccw(x1, y1, x2, y2, x3, y3):
    return (x2 - x1) * (y3 - y2) - (x3 - x2) * (y2 - y1)


idx = 0
while True:
    idx += 1
    n = int(sys.stdin.readline())
    if n == 0:
        break
    
    coord = [tuple(map(int, sys.stdin.readline().split())) for _ in range(n)]
    coord.sort(key=lambda x: (x[1], x[0]))

    a, b = coord.pop(0)
    coord.sort(key=lambda x: tangent(*x))

    stack = [(a, b), coord[0]]
    for i in range(1, n - 1):
        while len(stack) >= 2:
            if ccw(*stack[-2], *stack[-1], *coord[i]) <= 0:
                stack.pop()
            else:
                break
        stack.append(coord[i])
    
    if (len(stack) >= 3) and (ccw(*stack[-2], *stack[-1], *stack[0]) <= 0):
        stack.pop()
    
    ans = float('inf')

    for i in range(-1, len(stack) - 1):
        x1, y1 = stack[i]
        x2, y2 = stack[i + 1]

        a = y2 - y1
        b = x1 - x2
        c = x2 * y1 - x1 * y2
        
        k = (a ** 2 + b ** 2) ** 0.5
        d = 0
        for j in range(len(stack)):
            x, y = stack[j]
            d = max(d, abs(a * x + b * y + c) / k)

        ans = min(ans, d)
    
    ans = ceil(100 * ans) / 100
    print(f'Case {idx}: {ans:.2f}')