BZOJ2564: 集合的面积(闵可夫斯基和 凸包)

题意

题目链接

sol

这个东西的学名应该叫“闵可夫斯基和”。就是合并两个凸包

首先我们先分别求出给出的两个多边形的凸包。合并的时候直接拿个双指针扫一下，每次选最凸的点就行了。

复杂度\(o(nlogn + n)\)

#include<bits/stdc++.h>
#define ll long long 
//#define int long long 
using namespace std;
const int maxn = 1e6 + 10;
inline int read() {
    char c = getchar(); int x = 0, f = 1;
    while(c < '0' || c > '9') {if(c == '-') f = -1; c = getchar();}
    while(c >= '0' && c <= '9') x = x * 10 + c - '0', c = getchar();
    return x * f;
}
int n, m;
struct point {
    ll x, y;
    point operator - (const point &rhs) const {
        return {x - rhs.x, y - rhs.y};
    }
    point operator + (const point &rhs) const {
        return {x + rhs.x, y + rhs.y};
    }
    ll operator ^ (const point &rhs) const {
        return x * rhs.y - y * rhs.x;
    }
    bool operator < (const point &rhs) const {
        return x == rhs.x ? y < rhs.y : x < rhs.x;
    }
    bool operator == (const point &rhs) const {
        return x == rhs.x && y == rhs.y;
    }
    bool operator != (const point &rhs) const {
        return x != rhs.x || y != rhs.y;
    }
};
vector<point> v1, v2;
point q[maxn];
int top;
void insert(point a) {
    while(top > 1 && ((q[top] - q[top - 1]) ^ (a - q[top - 1])) < 0) top--;
    q[++top] = a;
}
void getconhull(vector<point> &v) {
    sort(v.begin(), v.end());
    q[++top] = v[0];
    for(int i = 1; i < v.size(); i++) if(v[i] != v[i - 1]) insert(v[i]);
    for(int i = v.size() - 2; i >= 0; i--) if(v[i] != v[i + 1]) insert(v[i]);
    v.clear(); 
    for(int i = 1; i <= top; i++) v.push_back(q[i]); top = 0;
}
void merge(vector<point> &a, vector<point> &b) {
    vector<point> c;
    q[++top] = a[0] + b[0]; 
    int i = 0, j = 0;
    while(i + 1 < a.size() && j + 1< b.size()) {
        point n1 = (a[i] + b[j + 1]) - q[top], n2 = (a[i + 1] + b[j]) - q[top];
        if((n1 ^ n2) < 0) 
            q[++top] = a[i + 1] + b[j], i++;
        else 
            q[++top] = a[i] + b[j + 1], j++; 
    }
    for(; i < a.size(); i++) q[++top] = a[i] + b[b.size() - 1];
    for(; j < b.size(); j++) q[++top] = b[j] + a[a.size() - 1];
    for(int i = 1; i <= top; i++) c.push_back(q[i]);
    ll ans = 0;
    //for(auto &g : c) printf("%d %d\n", g.x, g.y);
    for(int i = 1; i < c.size() - 1; i++) 
        ans += (c[i] - c[0]) ^ (c[i + 1] - c[0]);
    cout << ans;
}
signed main() {
    n = read(); m = read();
    for(int i = 1; i <= n; i++) {
        int x = read(), y = read();
        v1.push_back({x, y});
    }
    for(int i = 1; i <= m; i++) {
        int x = read(), y = read();
        v2.push_back({x, y});
    }
    getconhull(v1);
    getconhull(v2);
    merge(v1, v2);
    return 0;
}
/*
4 5
0 0 2 1 0 1 2 0
0 0 1 0 0 2 1 2 0 1
*/