[BOJ/Platinum 4] 백준 2244 민코프스키 합(C++)

문제 링크

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

2244번: 민코프스키 합

 

 

문제

다각형은 그 경계 위에 놓인 모든 점과 그 안의 모든 영역으로 구성되어 있다. 이러한 다각형 중에서 앞으로 이 문제에서 다룰 다각형은 다음과 같은 특성을 만족하는 것으로 한다.

1. 다각형 안의 임의의 두 점을 잇는 선분이 완전히 그 다각형 안에 속해 있다.
2. 세 개 이상의 꼭짓점으로 이루어져 있다.
3. 세 꼭짓점이 한 직선 위에 있는 경우는 없다.

이러한 특성을 만족하는 두 다각형 A, B가 있을 때, 이들의 민코프스키(Minkowski) 합은, A에 속하는 모든 영역의 좌표 (x1, y1)와 B에 속하는 모든 영역의 좌표 (x2, y2)에 대해, 있을 수 있는 모든 (x1 + x2, y1 + y2) 조합이 나타내는 영역의 도형이다. 다음은 두 삼각형과 이들의 민코프스키 합을 그림으로 나타낸 것이다.

두 다각형이 주어졌을 때, 두 다각형의 민코프스키 합을 구하는 프로그램을 작성하시오. 만약 민코프스키 합이 여러 개의 다각형으로 이루어진다면 다음의 우선순위에 따라 하나의 다각형만을 구하도록 한다. 번호가 작은 것이 우선순위가 높은 것이다.

1. 꼭짓점의 개수가 가장 작은 것
2. 면적이 가장 작은 것
3. 다각형을 이루는 모든 좌표들 중 최소 x좌표가 가장 작은 것
4. 다각형을 이루는 모든 좌표들 중 최소 y좌표가 가장 작은 것

입력

첫째 줄에 두 다각형 A와 B의 꼭짓점 개수 N과 M이 주어진다. (3 ≤ N, M ≤ 1,000) 다음 N개의 줄에는 다각형 A를 이루는 꼭짓점의 좌표가, 그 다음 M개의 줄에는 다각형 B를 이루는 꼭짓점의 좌표가 주어진다. 좌표는 x좌표와 y좌표가 빈칸을 사이에 두고 순서대로 주어지며, 반시계 방향으로 입력된다. 모든 좌표는 100,000,000을 넘지 않는 음이 아닌 정수이다.

출력

첫째 줄에 우리가 구하고자 하는 다각형의 꼭짓점의 개수를 출력한다. 다음 줄부터는 다각형을 이루는 꼭짓점의 x좌표와 y좌표를 한 줄에 한 쌍씩 반시계 방향으로 출력한다. 출력되는 첫 번째 꼭짓점은 x좌표가 가장 작은 점으로 하며, x좌표가 가장 작은 점이 여러 개 있을 경우 y좌표가 가장 작은 점으로 한다.

예제 입력 1

3 3
0 0
1 0
1 1
0 1
0 0
1 0

예제 출력 1

5
0 0
2 0
2 1
1 2
0 1

힌트

민코프스키(Minkowski, Hermann. 1864~1909)는 독일에서 활동한 러시아 수학자로 기하학에 공리계를 도입한 것으로 잘 알려진 힐베르트(Hilbert, David. 1862~1943)와 친교를 맺고 함께 괴팅켄 대학을 세계 수학의 중심지로 만들었다. 괴팅겐 대학은 20세기 들어 노벨상 수상자인 막스 보른, 제임스 프랑크, 베르너 하이젠베르크, 막스 폰 라우에 등 현대물리학의 대가들을 배출한 바 있으며 실제로 민코프스키 또한 <공간과 시간> 등의 저서에서 4차원적 시공간에 대해 논하며 아인슈타인의 상대성이론의 형성에도 공헌한 것으로 알려져 있다.

알고리즘 분류

• 그레이엄 스캔

풀이

다각형 A, B의 꼭짓점의 최대 개수는 1,000개이므로 최대 1,000,000개의 꼭짓점을 가지는 민코프스키 합이 나올 수 있다.

이것을 그레이엄 스캔을 통해 볼록 껍질을 찾고 꼭짓점의 개수를 출력하고 좌표를 반시계 방향으로 출력한다.

민코프스키 합의 꼭짓점의 좌표는 200,000,000가 최대이지만 CCW를 계산하면서 int32 범위를 초과할 수 있으니 long long 타입을 사용한다. 이거 때문에 1시간 날림.

코드

#include <iostream>
#include <vector>
#include <string>
#include <cmath>
#include <algorithm>
#define INF 2e9
#define LL long long
#define FASTIO cin.tie(0); cout.tie(0); ios::sync_with_stdio(false);

using namespace std;
struct POINT {
    LL X, Y;
};

int N, M, First;
LL X, Y, MinX, MinY;
vector<POINT> A, B, Point, CV;

void init() {
    MinX = INF;
    MinY = INF;
}

LL CCW(POINT A, POINT B, POINT C) {
    LL OP = ((A.X * B.Y) + (B.X * C.Y) + (C.X * A.Y));
    OP -= ((A.Y * B.X) + (B.Y * C.X) + (C.Y * A.X));
    return OP;
}

bool Comp(POINT A, POINT B) {
    LL NowCCW = CCW(Point[0], A, B);
    if (NowCCW != 0) {
        return (NowCCW > 0);
    }
    if (A.X != B.X) {
        return (A.X < B.X);
    }
    return (A.Y < B.Y);
}

void input() {
    cin >> N >> M;
    for (int i = 0; i < N; i++) {
        cin >> X >> Y;
        POINT Tmp;
        Tmp.X = X;
        Tmp.Y = Y;
        A.push_back(Tmp);
    }
    for (int i = 0; i < M; i++) {
        cin >> X >> Y;
        POINT Tmp;
        Tmp.X = X;
        Tmp.Y = Y;
        B.push_back(Tmp);
    }
}

void minkowski_Sum() {
    for (int i = 0; i < N; i++) {
        LL X1 = A[i].X;
        LL Y1 = A[i].Y;
        for (int j = 0; j < M; j++) {
            LL X2 = B[j].X;
            LL Y2 = B[j].Y;
            POINT Tmp;
            Tmp.X = X1 + X2;
            Tmp.Y = Y1 + Y2;
            Point.push_back(Tmp);
        }
    }
}

void graham_Scan() {
    for (int i = 0; i < Point.size(); i++) {
        if ((MinX > Point[i].X) || ((MinX == Point[i].X) && (MinY > Point[i].Y))) {
            MinX = Point[i].X;
            MinY = Point[i].Y;
            First = i;
        }
    }
    swap(Point[0], Point[First]);
    sort(Point.begin() + 1, Point.end(), Comp);
    for (int i = 0; i < Point.size(); i++) {
        while ((CV.size() >= 2) && (CCW(CV[CV.size() - 2], CV[CV.size() - 1], Point[i]) <= 0)) {
            CV.pop_back();
        };
        CV.push_back(Point[i]);
    }
}

void settings() {
    minkowski_Sum();
    graham_Scan();
}

void find_Answer() {
    cout << CV.size() << "\n";
    for (int i = 0; i < CV.size(); i++) {
        cout << CV[i].X << " " << CV[i].Y << "\n";
    }
}

int main() {
    FASTIO
    init();
    input();
    settings();
    find_Answer();

    return 0;
}