[BOJ 2244] 민코프스키 합

문제

---

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

풀이

---

일단 문제에 민코프스키 합이 여러 개의 다각형으로 이뤄지면 다음 우선순위에 따라 하나의 다각형만을 구하라고 돼있는데, 민코프스키 합이 disconnect하게 나오진 않을 것 같다.

정답을 x 좌표가 가장 작고, 그중에서도 y 좌표가 가장 작은 점부터 시작해 반시계 방향으로 출력해야 하므로 두 도형에서 각각 시작점을 찾는다.

그 두 시작점의 합이 민코프스키 합의 시작점이라는 것은 자명하다.

두 도형의 모든 변을 벡터로 취급해, 벡터 (0, -1)로부터 시계 반대 방향으로 돌아간 각도를 기준으로 정렬한다.

이 정렬된 벡터들을 시작점에 차례로 더해주면 민코프스키 합이 완성된다.

코드

---

import sys


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


n, m = map(int, sys.stdin.readline().split())

A = [tuple((*map(int, sys.stdin.readline().split()), i)) for i in range(n)]
B = [tuple((*map(int, sys.stdin.readline().split()), i)) for i in range(m)]

a = sorted(A)[0][2]
b = sorted(B)[0][2]

res = [(A[a][0] + B[b][0], A[a][1] + B[b][1])]

edges = []
for i in range(-1, n - 1):
    edges.append((A[i + 1][0] - A[i][0], A[i + 1][1] - A[i][1]))

for i in range(-1, m - 1):
    edges.append((B[i + 1][0] - B[i][0], B[i + 1][1] - B[i][1]))

edges.sort(key=tangent)

res.append((res[0][0] + edges[0][0], res[0][1] + edges[0][1]))

for i in range(1, n + m):
    x, y = res[-1]
    res.append((x + edges[i][0], y + edges[i][1]))
    if edges[i - 1][0] * edges[i][1] == edges[i - 1][1] * edges[i][0]:
        res.pop(-2)

res.pop()
print(len(res))
for x, y in res:
    print(x, y)