2244번: 민코프스키 합

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

#include<stdio.h>
#include<algorithm>
#define x first
#define y second
using namespace std;
const int MAX_N = 1000;
typedef long long ll;
typedef pair<ll, ll> point;
int cnt, top;
point a[MAX_N], b[MAX_N], c[MAX_N*MAX_N], stk[MAX_N*MAX_N];
ll ccw(point i, point j, point k) {
    return i.x*j.y + j.x*k.y + k.x*i.y - i.y*j.x - j.y*k.x - k.y*i.x;
}
bool comp(point i, point j) {
    ll t = ccw(c[0], i, j);
    return t>0 || !t && (i.x<j.x || i.x == j.x&&i.y<j.y);
}
int n, m;
int main() {
    scanf("%d %d", &n, &m);
    for (int i = 0; i < n; i++)
        scanf("%lld %lld", &a[i].x, &a[i].y);
    for (int i = 0; i < m; i++)
        scanf("%lld %lld", &b[i].x, &b[i].y);
    for (int i = 0; i < n; i++)
        for (int j = 0; j < m; j++)
            c[cnt++] = { a[i].x + b[j].x,a[i].y + b[j].y };
    sort(c, c + cnt);
    cnt = unique(c, c + cnt) - c;
    sort(c + 1, c + cnt, comp);
    for (int i = 0; i < cnt; i++) {
        while (top > 1 && ccw(stk[top - 2], stk[top - 1], c[i]) <= 0) top--;
        stk[top++] = c[i];
    }
    printf("%d\n", top);
    for (int i = 0; i < top; i++)
        printf("%lld %lld\n", stk[i].x, stk[i].y);
    return 0;
}