[BOJ 2699] 격자점 컨벡스헐

문제

---

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

풀이

---

볼록 껍질에 단순 다각형을 합친듯한 문제이다.

시작점을 찾은 뒤, tangent 값으로 정렬해 주는데 이번 문제는 시계 방향임에 유의해야 한다.

그리고 Graham scan을 이용해 볼록 껍질을 구해주고 출력하면 된다.

코드

---

import sys


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


def isline(x, y, z):
    return (y[1] - x[1]) * (z[0] - y[0]) == (z[1] - y[1]) * (y[0] - x[0])


for _ in range(int(sys.stdin.readline())):
    n = int(sys.stdin.readline())
    coord = []

    for __ in range(n // 5):
        data = list(map(int, sys.stdin.readline().split()))
        for i in range(5):
            coord.append((data[2 * i], data[2 * i + 1]))

    if n % 5:
        data = list(map(int, sys.stdin.readline().split()))
        for i in range(n % 5):
            coord.append((data[2 * i], data[2 * i + 1]))

    coord.sort(key=lambda x: (-x[1], x[0]))
    a, b = coord.pop(0)
    coord.sort(key=tangent)
    
    stack = [(a, b), coord[0]]
    idx = 0
    while idx < n - 2:
        idx += 1
        w1, w2 = coord[idx]
        while len(stack) >= 2:
            u1, u2 = stack[-2]
            v1, v2 = stack[-1]
            if (v1 - u1) * (w2 - v2) >= (v2 - u2) * (w1 - v1):
                stack.pop()
            else:
                break
        
        stack.append((w1, w2))
        if (len(stack) >= 3) and isline(stack[-3], stack[-2], stack[-1]):
            stack.pop(-2)

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

    print(len(stack))

    if len(stack) == 2:
        coord.append((a, b))
        coord.sort(key=lambda x: (-x[1], x[0]))
        print(*coord[0])
        print(*coord[-1])
        continue

    a, b = stack[0]
    if stack[1][0] == a:
        slope_start = float('inf')
    else:
        slope_start = (b - stack[1][1]) / (a - stack[1][0])
    
    idx = 1
    while True:
        idx += 1
        if idx == len(stack):
            break
        
        if stack[idx][0] == a:
            slope = float('inf')
        else:
            slope = (b - stack[idx][1]) / (a - stack[idx][0])
        
        if slope_start != slope:
            break

    print(a, b)
    for i in range(1, idx):
        print(*stack[idx - i])
    
    for i in range(len(stack) - idx):
        print(*stack[idx + i])