BOJ - 2699 - 공약수

import sys
import math

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):
                break
            convex.pop()
        convex.append(p3)
    return convex

def findStartPoint(position):
    x, y = -100, -100
    index = -100

    for i in range(len(position)):
        if position[i][1] > y:
            x = position[i][0]
            y = position[i][1]
            index = i

        if position[i][1] == y:
            if position[i][0] < x:
                x = position[i][0]
                y = position[i][1]
                index = i
    return index

def solution():
    P = int(sys.stdin.readline())
    for _ in range(P):
        N = int(sys.stdin.readline())
        position = []
        for _ in range(math.ceil(N/5)):
            arr = []
            arr = list(map(int, sys.stdin.readline().split()))
            for i in range(len(arr) // 2):
                position.append((arr[i * 2], arr[i * 2 + 1]))

        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])

        print(len(ccwtemp))
        d = findStartPoint(ccwtemp)
        for i in range(len(ccwtemp), 0, -1):
            print(ccwtemp[(i + d) % len(ccwtemp)][0], ccwtemp[(i + d) % len(ccwtemp)][1])

solution()

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