[백준] 1708 볼록 껍질, python

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

 

 

 

 

 

주어진 점들의 볼록 껍질의 꼭짓점의 개수를 구하는 문제이다.

 

 

볼록 껍질(convex hull)(1), Graham Scan 알고리즘, python

볼록 껍질(convex hull)(1), Graham Scan 알고리즘, python

 

 

 

볼록 껍질(convex hull)(2), Monotone Chain 알고리즘, python

볼록 껍질(convex hull)(2), Monotone Chain 알고리즘, python

 

그레이엄 스캔 알고리즘을 통해 볼록 껍질의 꼭짓점의 개수를 구해주었다.

 

 

 

import sys, math
input = sys.stdin.readline

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

# 외적으로 CCW체크
def ccw(p1,p2,p3):
    a,b = p2[0]-p1[0],p2[1]-p1[1]
    c,d = p3[0]-p1[0],p3[1]-p1[1]
    return a*d-b*c

points.sort(key=lambda p:(p[1],p[0]))
p0 = points[0]
points = points[1:]

# 점을 각도, 거리 순으로 정렬
points.sort(key=lambda p:(math.atan2(p[1]-p0[1],p[0]-p0[0]), (p0[0]-p[0])**2+(p0[1]-p[1])**2))

stack = [p0]
for p in points:
    # 스택의 상위 2개와 현재 점이 CW라면 스택에서 꺼냄
    while len(stack)>=2 and ccw(stack[-2],stack[-1],p) <= 0:
        stack.pop()
    stack.append(p)

print(len(stack))