처음에는 너무 쉬운 문제라고 생각했다.
고등학교 1학년때 배우는 점과 직선사이의 거리 공식을 이용하면 되는거 아닌가? 하고 10분만에 풀었다. (사실 제출조건이 까다로워서 좀 더 걸리기는 했다)
코드는 다음과 같다.
import sys,math
input = sys.stdin.readline
def lineeq(x1,y1,x2,y2):
return y2-y1,x1-x2,(x2-x1)*y1-(y2-y1)*x1
test = 1
while 1:
N = int(input())
if not N:
break
point = []
for _ in range(N):
point.append([*map(int,input().split())])
result = 1e9
line = []
for n in range(N):
a,b,c = lineeq(*point[n],*point[(n+1)%N])
denom = math.sqrt(a**2+b**2)
width = 0
for i in range(N):
width = max(width,abs(a*point[i][0]+b*point[i][1]+c)/denom)
result = min(result,width)
print("Case",str(test)+":","{:.2f}".format(math.ceil(result*100)/100))
test += 1
코드를 설명하면,
1. 모든 점에 대해서 현재 점과 다음점의 직선의 방정식을 세운다.
2. 점과 직선사이의 거리 공식으로 모든 점에 대해서 최대거리를 찾는다.
3. 1,2로 찾은 최대거리의 최솟값이 곧 슈트의 너비이다.
그런데 얼마 가지 않고 틀렸습니다가 떴다.
왜 틀린거지 하고 고민하다가 이 문제가 볼록껍질 문제라는 사실을 알게되었다.
2번에서 모든 점에 대해 거리를 찾을 때, 오목한 변의 직선을 가지고 하면 안되기 때문이다.
그래서 이 문제를 풀기 위해 볼록껍질 [백준 1708번] 볼록 껍질 (Python3) (tistory.com) 을 공부하였다.
이를 적용한 코드는 다음과 같다.
import sys,math
input = sys.stdin.readline
def lineeq(x1,y1,x2,y2):
return y2-y1,x1-x2,(x2-x1)*y1-(y2-y1)*x1
test = 1
while 1:
N = int(input())
if not N:
break
point = []
for _ in range(N):
x,y = map(int,input().split())
point.append((y,x))
point.sort()
cospoint = []
sy,sx = point[0]
for i in range(1,N):
y,x = point[i]
cospoint.append(((sx-x)/math.sqrt((x-sx)**2+(y-sy)**2),x,y))
cospoint.sort()
convex = [(sx,sy)]
for i in range(N-1):
cos,x,y = cospoint[i]
while len(convex)>1:
x1,y1,x2,y2 = *convex[-2],*convex[-1]
CCW = (x1-x2)*(y-y2)-(y1-y2)*(x-x2)
if CCW > 0:
convex.pop()
elif CCW == 0:
if (sx-x2)**2+(sy-y2)**2 > (sx-x)**2+(sy-y)**2:
x,y = convex.pop()
else:
convex.pop()
else:
break
convex.append((x,y))
N = len(convex)
result = 1e9
line = []
for n in range(N):
a,b,c = lineeq(*convex[n],*convex[(n+1)%N])
denom = math.sqrt(a**2+b**2)
width = 0
for i in range(N):
width = max(width,abs(a*convex[i][0]+b*convex[i][1]+c)/denom)
result = min(result,width)
print("Case",str(test)+":","{:.2f}".format(math.ceil(result*100)/100))
test += 1알고리즘은 처음 코드와 똑같고, 대신 모든 점에 대해서 하는것이 아닌 볼록껍질을 이루는 점만을 가지고 처음 코드를 실행하면 된다.
그리고 출력방식이 매우 까다로운데, 소수 두번째 자리까지 "올림" 을 해야하고, 케이스 번호까지 적어야 한다... 매우 짜증날 수 있다.
여담) 내 코드가 파이썬 기준 성능 1위가 되었다.
