본문 바로가기

카테고리 없음

[백준 4225번] 쓰레기 슈트 (Python3)

처음에는 너무 쉬운 문제라고 생각했다.

고등학교 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위가 되었다.