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
*/