描述

給一些多邊形求重疊面積

分析

半平面交的模版

注意別少加了直線

#include #include #include #include using namespace std;struct Point {double x, y;Point(double x=0, double y=0):x(x),y(y) { } };typedef Point Vector;Vector operator + (const Vector& A, const Vector& B) { return Vector(A.x+B.x, A.y+B.y); } Vector operator - (const Point& A, const Point& B) { return Vector(A.x-B.x, A.y-B.y); } Vector operator * (const Vector& A, double p) { return Vector(A.x*p, A.y*p); } double Dot(const Vector& A, const Vector& B) { return A.x*B.x + A.y*B.y; } double Cross(const Vector& A, const Vector& B) { return A.x*B.y - A.y*B.x; } double Length(const Vector& A) { return sqrt(Dot(A, A)); } Vector Normal(const Vector& A) {double L = Length(A);return Vector(-A.y/L, A.x/L); }double PolygonArea(vectorp) { int n = p.size(); double area = 0; for(int i = 1; i < n-1; i++) area += Cross(p[i]-p[0], p[i+1]-p[0]); return area/2; } // 有向直線。它的左邊就是對應的半平面 struct Line { Point P; // 直線上任意一點 Vector v; // 方向向量 double ang; // 極角，即從x正半軸旋轉到向量v所需要的角（弧度） Line() {} Line(Point P, Vector v):P(P),v(v) { ang = atan2(v.y, v.x); } bool operator < (const Line& L) const { return ang < L.ang; } }; // 點p在有向直線L的左邊（線上不算） bool OnLeft(const Line& L, const Point& p) { return Cross(L.v, p-L.P) > 0; } // 二直線交點，假定交點惟一存在 Point GetLineIntersection(const Line& a, const Line& b) { Vector u = a.P-b.P; double t = Cross(b.v, u) / Cross(a.v, b.v); return a.P+a.v*t; } const double INF = 1e8; const double eps = 1e-6; // 半平面交主過程 vectorHalfplaneIntersection(vectorL) { int n = L.size(); sort(L.begin(), L.end()); // 按極角排序 int first, last; // 雙端隊列的第一個元素和最后一個元素的下標 vectorp(n); // p[i]為q[i]和q[i+1]的交點 vectorq(n); // 雙端隊列 vectorans; // 結果 q[first=last=0] = L[0]; // 雙端隊列初始化為只有一個半平面L[0] for(int i = 1; i < n; i++) { while(first < last && !OnLeft(L[i], p[last-1])) last--; while(first < last && !OnLeft(L[i], p[first])) first++; q[++last] = L[i]; if(fabs(Cross(q[last].v, q[last-1].v)) < eps) { // 兩向量平行且同向，取內側的一個 last--; if(OnLeft(q[last], L[i].P)) q[last] = L[i]; } if(first < last) p[last-1] = GetLineIntersection(q[last-1], q[last]); } while(first < last && !OnLeft(q[first], p[last-1])) last--; // 刪除無用平面 if(last - first <= 1) return ans; // 空集 p[last] = GetLineIntersection(q[last], q[first]); // 計算首尾兩個半平面的交點 // 從deque復制到輸出中 for(int i = first; i <= last; i++) ans.push_back(p[i]); return ans; } int main() { int n, m; scanf("%d", &n); vectorL; for(int i = 0; i < n; i++) { vectorp; scanf("%d", &m); for(int j = 0; j < m; j++) { double x, y; scanf("%lf %lf", &x, &y); p.push_back(Point(x, y)); if(j) L.push_back(Line(p[j], p[j]-p[j-1])); } L.push_back(Line(p[m-1], p[0]-p[m-1])); } vectorp = HalfplaneIntersection(L); double ans = PolygonArea(p); printf("%.3lf", ans); return 0; }

總結

以上是生活随笔為你收集整理的BZOJ-2618-凸多边形-CQOI2006的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內容還不錯，歡迎將生活随笔推薦給好友。