[백준 3679번] 단순 다각형 (Python3)

import sys,math
input = sys.stdin.readline

for _ in range(int(input())):
  data = [*map(int,input().split())]; N = data[0]
  co = sorted([(data[i*2+2],data[i*2+1],i) for i in range(N)])
  
  y0,x0,n0 = co[0]; stack = []
  for i in range(1,N):
    y,x,n = co[i]
    d = math.sqrt((x-x0)**2+(y-y0)**2)
    stack.append((int((x0-x)/d*1e9),int(d*1e9),n))
  stack.sort()
  
  cos0 = stack[-1][0]
  for i in range(N-1):
    if stack[-i-1][0]!=cos0:
      break
  stack = stack[:-i]+sorted(stack[-i:],reverse=True)
  print(n0,*map(lambda x:x[2],stack))

볼록껍질 응용(?) 문제

 

볼록껍질 문제에서 그레이엄 스캔을 하기 전에 점들을 각도에 따라 정렬을 해주게 된다. 이 문제는 그냥 이때의 정렬된 순서를 출력하면 끝나는 문제이다. 그래서 구현난이도는 볼록껍질의 하위호환 문제라고 볼 수 있다.

 

약간의 예외처리가 필요한데,

1. 각도가 같은 경우에는 거리의 오름차순으로 정렬한다.

2. 맨 마지막 값들의 각도가 같은 경우에는 거리의 내림차순으로 정렬한다.

3. 소수를 그대로 계산하면 각도가 같은 경우에도 다르다고 판단하고 잘못된 결과를 도출할 수 있으니 소수점 10의자리 정도에서 반올림해주는 것이 좋다.

 

3번 때문에 애먹은 문제였다. 각도의 계산을 코사인으로 해주었는데, 소수점 차이때문에 계속 틀렸습니다가 나왔었다. 따라서 소수에 10**9를 곱하고 int형으로 변환하자 맞게되었다.

 

 

오늘의 교훈) 볼록껍질 정렬과정에서 소수점 차이 조심