Maple Roundup(BOJ 6962)

볼록껍질을 이루는 선의 길이를 출력하면 되는 문제이다.

1. 모든 점을 돌면서 볼록껍질을 이루는 점들을 찾는다

2. 그 모든 점들의 이루는 길이를 다 더한다

3. 소숫점 2번째 자리까지 출력한다.

import sys
from collections import deque
import math
input = sys.stdin.readline

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] # 시작점과 끝점이 중복되므로 제거

def getDist(p1,p2):
    return math.sqrt((p1[0] - p2[0])**2 + (p1[1] - p2[1])**2)

N = int(input())
for _ in range(N):
    k = int(input())
    points = [list(map(int, input().split())) for _ in range(k)]
    c = convex_hull(points) # 볼록껍질을 이루는 점들
    total = 0
    for i in range(len(c)):
        total += getDist(c[i-1], c[i]) # 볼록 껍질을 이루는 점들의 길이를 다 더함
    print(f"{total:.2f}")