BOJ - 17403 - 가장 높고 넓은 성

import sys

def getDegree(p1, p2):
    return p2[0] - p1[0], p2[1] - p1[1]

def ccw(p1, p2, p3):
    v, u = getDegree(p1, p2), getDegree(p1, p3)
    if v[0] * u[1] > v[1] * u[0]: return True
    else: return False

def convex_hull(position):
    convex = []

    for p3 in position:
        while len(convex) >= 2:
            p1, p2 = convex[-2], convex[-1]
            if ccw(p1, p2, p3) == 1:
                break
            convex.pop()
        convex.append(p3)
    return convex

def solution():
    N = int(sys.stdin.readline())
    position = []
    for _ in range(N):
        position.append(list(map(int, sys.stdin.readline().split())))
    check = position
    ret = 0
    while True:

        position = sorted(position, key=lambda x:(x[0], x[1]))
        ccwtemp = convex_hull(position)
        position.reverse()
        temp = convex_hull(position)

        for i in range(1, len(temp)-1):
            ccwtemp.append(temp[i])

        if len(ccwtemp) < 3:
            for arr in ccwtemp:
                check[check.index(arr)] = -1
            break

        tempdata = []
        for i in range(len(position)):
            if position[i] not in ccwtemp:
                tempdata.append(position[i])
            else:
                check[check.index([position[i][0], position[i][1]])] = ret
        position = tempdata
        ret += 1

    for c in check:
        try:
            print(c + 1, end = ' ')
        except Exception as e:
            print(0, end = ' ')

solution()

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