BOJ 3679 - 단순 다각형 링크
(2022.11.09 기준 P4)

• 수정 내역

1. 2024.03.10 1차 수정 (첫 번째 그림이 다른 그림과 점의 집합이 다른 것을 수정)

문제

평면 위의 점의 집합이 주어졌을 때, 집합의 모든 점이 다각형의 꼭짓점이 되야 하고, 다각형의 두 선분은 교차할 수 없을 때, 다각형을 이루도록 점을 연결하는 순서 출력

알고리즘

볼록 껍질을 최대한 만들어서 해도 연결 해도 된다만, 볼록 다각형이 아니어도 되므로 볼록 껍질의 아래만 구해서 점들을 연결해도 된다. 자세한 내용은 풀이에서 후술.

풀이

위와 같은 점의 집합이 주어졌다고 가정하자.

일직선인 경우도 포함하여 볼록 껍질의 아래를 구해보자.
그리고 나머지 점들을 x, y 오름차순으로 정렬해 순서대로 연결해보자.

그러면 위와 같이 연결될 것이다. 볼록 껍질의 아래의 양 끝과 나머지 점들의 이은 선 양 끝을 연결하면

문제에서 원하는 다각형이 완성된다.

이 문제가 원하는 다각형은 볼록 다각형이 아니다. 단순히 선분이 교차하지 않게끔 점들을 이으면 되는 것이다. 그럼 결국 볼록 껍질의 아래를 구하면 다른 나머지 점들은 그 볼록 껍질의 아래를 벗어나지 않게 된다. 그러면 자연스럽게 나머지 점들은 정렬하여 이어주면 된다. 그러면 볼록 껍질의 아래가 나머지 점들을 담고 있는 접시 모양이 되는 것이다.

코드

import sys; input = sys.stdin.readline

def ccw(a, b, c): # a-b-c가 반시계 방향인지 검사
    return (a[0] * b[1] + b[0] * c[1] + c[0] * a[1]) - (a[1] * b[0] + b[1] * c[0] + c[1] * a[0])

def solve():
    n, *lst = map(int, input().split())

    # 점을 차례대로 정리
    points = []
    for i in range(n):
        points.append([lst[i * 2], lst[i * 2 + 1], i])

    # monotone chain을 통해 볼록 껍질의 아래를 구할 것이다.
    # 점들을 오름차순으로 정렬
    points.sort()
    used = [False] * n # 점이 볼록 껍질의 아래에 쓰였는지 판별할 배열
    convex_hull_down = []
    for i in range(n):
        while len(convex_hull_down) > 1:
            # 일직선인 경우도 넣자.
            if ccw(convex_hull_down[-2], convex_hull_down[-1], points[i]) >= 0:
                break
            p = convex_hull_down.pop()
            used[p[2]] = False
        convex_hull_down.append(points[i])
        used[points[i][2]] = True

    # 볼록 껍질의 아래에 쓰이지 않은 점들을 정렬된 순서대로 담자.
    answer = []
    for x, y, i in points:
        if not used[i]:
            answer.append(i)

    # 볼록 껍질의 아래를 연결. 단, 반대로 연결해야 한다.
    for i in range(len(convex_hull_down) - 1, -1, -1):
        answer.append(convex_hull_down[i][2])

    print(*answer)

for _ in range(int(input())):
    solve()

여담

어떻게 풀어내야 할지 생각이 좀 필요한 문제였다.
처음엔 볼록 껍질을 최대한 겹겹이 구해서 연결시키려다가 이건 코너 케이스가 많겠다 싶어서 다른 방법을 생각하다가 이 방법을 생각해내었다.
뿌-듯.