[BOJ 2244 // C++] 민코프스키 합

※ 글쓴이는 취미로 코딩을 익혀보는 사람이라 정확하지 않은 내용을 담고 있을 수 있다 ※

 

이번에 볼 문제는 백준 2244번 문제인 민코프스키 합이다.
문제는 아래 링크를 확인하자.

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

2244번: 민코프스키 합

두 볼록한(convex) 다각형 영역의 벡터합은 다시 볼록한 다각형 영역이 되고, 그 꼭짓점은 기존 다각형의 꼭짓점의 벡터합들로 구성된다.

 

이를 이용해, 가능한 N*M가지 꼭짓점 후보를 이용해 convex hull을 구하는 것으로 문제를 해결하자.

 

아래는 제출한 소스코드이다.

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
typedef long long ll;
typedef pair<ll, ll> pll;

int N;
pll points[1000000];
pll pA[1000], pB[1000];
vector<pll> upperhull; // leftmost x의 lowermost y부터 rightmost x의 uppermost y까지
vector<pll> lowerhull;

int CCW(pll& A, pll& B, pll& C) {
	ll ccw = (B.first - A.first) * (C.second - A.second) - (B.second - A.second) * (C.first - A.first);
	if (ccw > 0) return 1;
	else if (ccw < 0) return -1;
	else return 0;
}

void andrew_algorithm() {
	sort(points, points + N);

	//upperhull
	for (int i = 0; i < N; i++) {
		auto& cur = points[i];
		int cursize = upperhull.size();
		while (cursize > 1) {
			auto& L = upperhull[cursize - 2], & M = upperhull[cursize - 1];
			if (CCW(L, M, cur) != -1) upperhull.pop_back(), cursize--;
			else break;
		}
		upperhull.emplace_back(cur);
	}

	//lowerhull
	for (int i = 0; i < N; i++) {
		auto& cur = points[i];
		int cursize = lowerhull.size();
		while (cursize > 1) {
			auto& L = lowerhull[cursize - 2], & M = lowerhull[cursize - 1];
			if (CCW(L, M, cur) != 1) lowerhull.pop_back(), cursize--;
			else break;
		}
		lowerhull.emplace_back(cur);
	}
}

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);

	int X, Y; cin >> X >> Y;
	for (int i = 0; i < X; i++) cin >> pA[i].first >> pA[i].second;
	for (int j = 0; j < Y; j++) cin >> pB[j].first >> pB[j].second;

	for (int i = 0; i < X; i++) {
		for (int j = 0; j < Y; j++) {
			points[N++] = make_pair(pA[i].first + pB[j].first, pA[i].second + pB[j].second);
		}
	}

	andrew_algorithm();

	cout << upperhull.size() + lowerhull.size() - 2 << '\n';

	for (int i = 0; i < lowerhull.size() - 1; i++) cout << lowerhull[i].first << ' ' << lowerhull[i].second << '\n';
	for (int i = upperhull.size() - 1; i > 0; i--) cout << upperhull[i].first << ' ' << upperhull[i].second << '\n';
}