[BOJ 1708] 볼록 껍질

문제

---

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

풀이

---

첫 볼록 껍질 (Convex Hull) 문제이다.

점의 집합이 주어졌을 때, 볼록 껍질을 이루는 점의 개수를 구하는 문제이다.

나는 Graham Scan 알고리즘을 사용해 풀었다.

코드

---

import sys


def tangent(x, y):
    if x == a:
        return 1, y
    if x > a:
        return 0, (y - b) / (x - a), x
    if x < a:
        return 2, (y - b) / (x - a), x


def ccw(x1, y1, x2, y2, x3, y3):
    return (x2 - x1) * (y3 - y2) - (x3 - x2) * (y2 - y1)


n = int(sys.stdin.readline())

coord = [tuple(map(int, sys.stdin.readline().split())) for _ in range(n)]
coord.sort(key=lambda x: (x[1], x[0]))
a, b = coord.pop(0)
coord.sort(key=lambda x: tangent(*x))

stack = [(a, b), coord[0]]

for i in range(1, n - 1):
    while len(stack) >= 2:
        if ccw(*stack[-2], *stack[-1], *coord[i]) <= 0:
            stack.pop()
        else:
            break
    stack.append(coord[i])

if (len(stack) >= 3) and (ccw(*stack[-2], *stack[-1], *stack[0]) <= 0):
    stack.pop()

print(len(stack))