민코프스키 합 (백준 2244)

안녕하세요. 오늘은 민코프스키 합을 구해볼 거예요.

문제

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

아이디어

문제를 읽어보면 두가지를 알 수 있습니다.
1. 무조건 하나의 다각형만 나온다.
2. 그 다각형의 꼭짓점들은 모두 처음 두 다각형의 꼭짓점의 합 안에 있다.
즉, 맨 처음 다각형의 모든 꼭짓점들에 대해서 합을 구한 다음, 그 값들을 볼록껍질 해서 출력하면 됩니다.

소스코드

#include <iostream>
#include <vector>
#include <algorithm>
#define ll long long
#define pii pair <ll,ll>
using namespace std;

ll CCW(pii A, pii B, pii C)
{
    ll ax = A.first, ay = A.second, bx = B.first, by = B.second, cx = C.first, cy = C.second;
    ll ccw = ax * (by - cy) + bx * (cy - ay) + cx * (ay - by);
    if (ccw < 0) return -1;
    if (ccw > 0) return 1;
    return 0;
}
ll dis(pii A, pii B)
{
    return (A.first - B.first) * (A.first - B.first) + (A.second - B.second) * (A.second - B.second);
}

pii low_dot;
bool cmp(pii A, pii B)
{
    if (CCW(low_dot, A, B) > 0) return true;
    if (CCW(low_dot, A, B) == 0) return dis(low_dot, A) < dis(low_dot, B);
    return false;
}

ll stk[1010101] = { 0 }, top = 2;
vector <pii> make_convex(vector <pii> v)
{
    ll N = v.size();
    sort(v.begin(), v.end());
    low_dot = v[0];
    sort(v.begin(), v.end(), cmp);

    stk[0] = 0; stk[1] = 1;
    for (int i = 2; i < N; i++)
    {
        while (top >= 2 && CCW(v[i], v[stk[top - 2]], v[stk[top - 1]]) <= 0)
            top--;
        stk[top++] = i;
    }

    vector <pii> ans;
    for (int i = 0; i < top; i++)
        ans.push_back(v[stk[i]]);

    return ans;
}

int main(void)
{
    ios_base::sync_with_stdio(false); cin.tie(NULL);
    ll N, M;
    vector <pii> A, B;

    cin >> N >> M;
    for (int i = 0; i < N; i++)
    {
        ll a, b;
        cin >> a >> b;
        A.push_back({ a,b });
    }
    for (int i=0;i<M;i++)
    {
        ll a, b;
        cin >> a >> b;
        B.push_back({ a,b });
    }

    vector <pii> v;
    for (int i = 0; i < N; i++)
        for (int j = 0; j < M; j++)
            v.push_back({ A[i].first + B[j].first,A[i].second + B[j].second });

    v = make_convex(v);
    cout << v.size() << "\n";
    for (pii temp : v)
        cout << temp.first << ' ' << temp.second << "\n";
}

감사합니다.