[백준] 17403 - 가장 높고 넓은 성 Python

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

17403번: 가장 높고 넓은 성

n 개의 표지판을 사용해 각 층별로 가장 넓은 면적을 확보하면서 가장 높이 성을 쌓았을 때, 각 표지판들이 몇 번째 층고에 사용되었는지 구하는 문제다.

1층부터 최대한 넓은 면적을 확보하기 위해 모든 표지판들의 좌표를 이용해 볼록껍질을 구성한다. 볼록 껍질에서 꼭지점을 이루는 점들이 표지판의 위치가 된다. 볼록 껍질 내부에 있거나 꼭지점이 아닌 변 위에 있는 점은 볼록 껍질을 구성하지 못한 점이다. 이러한 표지판들을 다음 시행에 사용하기 위한 배열에 추가힌다. 다음 시행인 2층에서는 1층에서 볼록껍질을 구성하지 못했던 표지판들의 배열을 이용해 볼록껍질을 구성하는 표지판들을 찾는다. 다음 층도 마찬가지로 진행한다.

넓이가 0 인 층은 허용되지 않기 떄문에 볼록껍질을 구성하는 꼭짓점들의 개수가 3개 미만이라면 다음 시행으로 넘어가지 않고 정리한다.

추가로 각 표지판들이 어느 층고에 위치한 표지판인지 알아야 한다. 각 표지판이 위치하는 층고를 나타내는 배열 d 를 표지판 개수만큼 0 으로 초기화한 후, 층마다 볼록껍질을 구성할 때 어느 층고에 위치해 있는지 입력해준다.

코드는 다음과 같다.

from sys import stdin
from functools import cmp_to_key

def distance(p1,p2):
    return (p2[0]-p1[0])**2 + (p2[1]-p1[1])**2

def ccw(p1,p2,p3):
    return (p2[0]-p1[0])*(p3[1]-p1[1]) - (p3[0]-p1[0])*(p2[1]-p1[1])
    
def compare(p1,p2):
    global p
    s = ccw(p,p1,p2)
    if s == 0:
        return distance(p,p1) - distance(p,p2)
    return -s

def graham_scan(arr):
    global p,f
    arr.sort()
    p = arr[0]
    arr[1:] = sorted(arr[1:],key=cmp_to_key(compare))
    stack = []
    next_arr = []
    for p in arr:
        while len(stack) >= 2 and ccw(stack[-2],stack[-1],p) <= 0:
            next_arr.append(stack.pop())
        stack.append(p)
    if len(stack) < 3:
        return stack
    for p in stack:
        d[p[2]] = f
    f += 1
    return next_arr

N = int(stdin.readline())
d = [0]*N
arr = []
for i in range(N):
    x,y = map(int,stdin.readline().split())
    arr.append((x,y,i))

f = 1
while len(arr) > 2:
    arr = graham_scan(arr)

print(*d)