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 */
上一篇: 和气生财才是王道嘛
下一篇: java队列Queue及阻塞队列