볼록 껍질

기하학 문제이다.

ccw(Counter Clockwise) 세점의 관계를 알 수 있는 공식(?)이다.

def ccw(p1, p2, p3):
    return (p2[0] - p1[0]) * (p3[1] - p1[1]) - (p2[1] - p1[1]) * (p3[0] - p1[0])

ccw의 return값이 양수면 시계방향, 음수면 반시계방향, 0이면 직선상에 놓여있다는 뜻 이다.

입력받은 점들의 상관관계를 ccw함수를 통해 확인하고 lower, upper list에 추가한다.

def convex_hull(points):
    points = sorted(points)
    lower = [] # 왼쪽에서 오른쪽으로
    for p in points:
        while len(lower) >= 2 and ccw(lower[-2], lower[-1], p) <= 0: # <= 0 이면 같은 직선에 있는 점도 포함
            lower.pop()
        lower.append(p)
    upper = [] # 오른쪽에서 왼쪽으로
    for p in reversed(points):
        while len(upper) >= 2 and ccw(upper[-2], upper[-1], p) <= 0:
            upper.pop()
        upper.append(p)
    return lower[:-1] + upper[:-1] # 시작점과 끝점이 중복되므로 제거

볼록껍질을 이루는 각 점의 갯수를 출력한다.

전체코드

def ccw(p1, p2, p3):
    return (p2[0] - p1[0]) * (p3[1] - p1[1]) - (p2[1] - p1[1]) * (p3[0] - p1[0])

def convex_hull(points):
    points = sorted(points)
    lower = [] # 왼쪽에서 오른쪽으로
    for p in points:
        while len(lower) >= 2 and ccw(lower[-2], lower[-1], p) <= 0: # <= 0 이면 같은 직선에 있는 점도 포함
            lower.pop()
        lower.append(p)
    upper = [] # 오른쪽에서 왼쪽으로
    for p in reversed(points):
        while len(upper) >= 2 and ccw(upper[-2], upper[-1], p) <= 0:
            upper.pop()
        upper.append(p)
    return lower[:-1] + upper[:-1] # 시작점과 끝점이 중복되므로 제거

n = int(input())
points = [list(map(int, input().split())) for _ in range(n)]

print(len(convex_hull(points)))