선영이는 쓰레기를 편하게 버리기 위해서 빌딩에 쓰레기 슈트를 만들었다. 쓰레기 슈트는 빌딩에 설치할 수 있는 속이 빈 튜브다. 튜브로 쓰레기를 떨어뜨리면, 쓰레기는 지하실까지 떨어지게 된다.
쓰레기 슈트를 만드는 일은 매우 어려운 일이다. 사람들이 무엇을 버릴지 알 수 없기 때문에, 쓰레기 슈트에 들어가지 않는 쓰레기를 버린다면, 슈트가 막혀버릴 수 있기 때문이다. 쓰레기 슈트를 만드는데 드는 비용은 그 크기에 비례한다. 따라서, 최대한 작게 만드는 것이 효율적이다.
먼저, 쓰레기 슈트를 만드는 문제를 2차원으로 단순화 시켜보자. 슈트는 일정한 너비를 가지고 있고, 다각형으로 모델링된 물체를 이 곳의 상단에 넣을 수 있다.
물체를 넣기 전에, 슈트에 들어갈 수 있게 돌려야 할 수도 있다. 슈트에 던진 이후에는 일직선으로 아래로 떨어지고, 그 동안 물체는 회전하지 않는다.
아래 그림은 물체를 쓰레기 슈트에 들어갈 수 있게 회전시킨 다음 버리는 그림이다.
어떤 물체가 주어진다. 이 물체가 통과할 수 있는 가장 작은 슈트의 너비를 구하는 프로그램을 작성하시오.
입력은 여러 개의 테스트 케이스로 이루어져 있다. 각 테스트 케이스의 첫째 줄에는 물체(다각형)의 꼭짓점의 개수 n이 주어진다. (3 ≤ n ≤ 100)
다음 n개 줄에는 꼭짓점의 좌표 xi와 yi가 주어진다. (0 ≤ xi, yi ≤ 104) 꼭짓점은 다각형을 이루는 순서대로 주어진다.
입력으로 주어지는 다각형의 좌표는 모두 서로 다르며, 다각형의 변은 교차하지 않는다. 엄밀히 따지면, 인접한 변은 한 꼭짓점을 공유한다는 예외가 하나 있다. 물론, 이 경우는 교차하는 것으로 생각하지 않는다.
마지막 테스트 케이스의 다음 줄에는 0이 하나 주어진다.
출력
각 테스트 케이스마다 케이스 번호와 가장 작은 쓰레기 슈트의 너비를 출력한다. 너비는 가장 가까운 0.01의 배수로 올림하여 소수점 둘째 자리까지 출력한다.
입력 예시
3
0 0
3 0
0 4
4
0 10
10 0
20 10
10 20
0
출력 예시
Case 1: 2.40
Case 2: 14.15
풀이
볼록 껍질(Convex Hull) 알고리즘, 그 중에서도 정렬 시간복잡도가 소요되는 그레이엄 스캔을 이용하는 문제.
어떤 변을 기준으로 쓰레기 슈트에 딱 맞게 넣으려면, 그 변과 가장 멀리 떨어진 점이 슈트의 양 끝에 맞닿도록 떨어뜨리는 방법이 있다. 즉 변과 가장 멀리 떨어진 점과의 거리가 슈트의 크기가 된다. 모든 변에 대해 이를 구한 다음, 그 최솟값을 출력하면 된다.
단, 이 변들은 다각형의 최외각 볼록껍질이라는 점을 명심해야 한다. 위 그림을 다시 살펴보면, 오목히 파인 구간의 점은 거리 연산에 영향을 주지 못하며, 이 구간의 변 하나를 기준으로 삼는다면 그 하나를 제외한 나머지 변들이 최소 범위를 벗어나 버린다(오목 구간이므로, 지정한 슈트의 범위를 벗어나는 방향으로 변이 이어짐을 알 수 있다). 즉 볼록 껍질을 구해야 한다.
그레이엄 스캔은 CCW 알고리즘을 기반으로 한다. 또한 다음과 같이 진행된다.
확실히 볼록 껍질 내에 있다고 볼 수 있는 점 하나를 선정한다(x값 혹은 y값이 제일 끝값인 점이 대표적이다)
그 점을 기준으로 각도가 증가하는 순으로 정렬한다.
이제 첫 번째 점(기준점)과 두 번째 점을 스택에 차례로 저장하고, 차례로 순회한다.
만약 현재 시점의 점과 스택의 직전의 점 2개가 ccw 결과 시계방향 회전이라면, 오목 구간을 생성하므로 조건을 충족할 때까지 스택을 pop한다.
그렇지 않다면 스택에 push한다.
이 모든 진행을 마친 후 스택에 남은 점들이 볼록 껍질을 이루는 점이 되며, 볼록 껍질의 순서가 된다.
풀이 코드
from functools import cmp_to_key
import sys
import math
input = sys.stdin.readline
MAX = float('inf')
def ccw(a, b, c) :
return (a[0]*b[1] + b[0]*c[1] + c[0]*a[1]) - (a[1]*b[0] + b[1]*c[0] + c[1]*a[0])
def cmp(a, b) :
if ccw(ref, a, b) < 0 :
return 1
else :
return -1
def convex_hull(points) :
stk = points[:2]
for point in points[2:] :
while len(stk) > 1 and ccw(stk[-2], stk[-1], point) < 0 :
stk.pop()
stk.append(point)
return stk
def distance(target, p0, p1) :
if p0[0] == p1[0] :
return abs(target[0] - p0[0])
if p0[1] == p1[1] :
return abs(target[1] - p0[1])
a, b = (p1[1] - p0[1]) / (p1[0] - p0[0]), -1
c = -a * p0[0] + p0[1]
return abs( a*target[0] + b*target[1] + c ) / (a**2 + b**2) ** 0.5
def solve(idx) :
global ref
N = int(input())
if N == 0 :
return False
points = [list(map(int, input().split())) for _ in range(N)]
ref, *points = sorted(points)
points.sort(key = cmp_to_key(cmp))
result = convex_hull([ref] + points)
length = len(result)
ans = MAX
for i in range(length) :
k = (i + 1) % length
tmp = 0.
for j in range(length) :
tmp = max(tmp, distance(result[j], result[i], result[k]))
ans = min(ans, tmp)
print('Case {:d}: {:0.02f}'.format(idx, math.ceil(ans*100) / 100.0))
return True
idx = 1
while True :
if not solve(idx) :
break
idx += 1
