欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页  >  IT编程

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

程序员文章站 2022-12-16 09:16:37
题意 "题目链接" Sol 这个东西的学名应该叫“闵可夫斯基和”。就是合并两个凸包 首先我们先分别求出给出的两个多边形的凸包。合并的时候直接拿个双指针扫一下,每次选最凸的点就行了。 复杂度$O(nlogn + n)$ cpp include define LL long long // define ......

题意

题目链接

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