首页 > 代码库 > BZOJ 2618 CQOI 2006 凸多边形 半平面交
BZOJ 2618 CQOI 2006 凸多边形 半平面交
题目大意:给出n个凸多边形,求这些多边形的面积的交。
思路:犯傻了。。以后看到凸多边形第一时间就要想到半平面交啊。。多明显啊,半天愣着没想出来。
CODE:
#include <cmath> #include <cstdio> #include <iomanip> #include <cstring> #include <iostream> #include <algorithm> #define MAX 6100 #define EPS 1e-10 #define DCMP(a) (fabs(a) < EPS) using namespace std; struct Point{ double x,y; Point(double _ = .0,double __ = .0):x(_),y(__) {} Point operator -(const Point &a)const { return Point(x - a.x,y - a.y); } Point operator +(const Point &a)const { return Point(x + a.x,y + a.y); } Point operator *(double a)const { return Point(x * a,y * a); } void Read() { scanf("%lf%lf",&x,&y); } }p[MAX],temp[600]; struct Line{ Point p,v; double alpha; Line(Point _,Point __):p(_),v(__) {} Line() {} bool operator <(const Line &a)const { return alpha < a.alpha; } void Calc() { alpha = atan2(v.y,v.x); } }line[MAX],q[MAX]; int k,cnt; int lines; inline double Cross(const Point &a,const Point &b) { return a.x * b.y - a.y * b.x; } inline void MakeLine(const Point &a,const Point &b) { line[++lines] = Line(a,b - a); } inline bool OnLeft(const Point &p,const Line &l) { return Cross(l.v,p - l.p) > 0; } inline Point GetIntersection(const Line &l1,const Line &l2) { Point u = l1.p - l2.p; double t = Cross(l2.v,u) / Cross(l1.v,l2.v); return l1.p + l1.v * t; } double HalfplanIntersection() { int front = 1,tail = 1; q[1] = line[1]; for(int i = 2; i <= lines; ++i) { while(front < tail && !OnLeft(p[tail - 1],line[i])) --tail; while(front < tail && !OnLeft(p[front],line[i])) ++front; if(DCMP(Cross(q[tail].v,line[i].v))) q[tail] = OnLeft(q[tail].p,line[i]) ? q[tail]:line[i]; else q[++tail] = line[i]; if(front < tail) p[tail - 1] = GetIntersection(q[tail],q[tail - 1]); } while(front < tail && !OnLeft(p[tail - 1],q[front])) --tail; p[tail] = GetIntersection(q[tail],q[front]); if(tail - front <= 1) return .0; double re = .0; for(int i = front; i < tail; ++i) re += Cross(p[i],p[i + 1]); re += Cross(p[tail],p[front]); return re / 2.0; } int main() { cin >> k; for(int i = 1; i <= k; ++i) { scanf("%d",&cnt); for(int j = 1; j <= cnt; ++j) temp[j].Read(); for(int j = 1; j < cnt; ++j) MakeLine(temp[j],temp[j + 1]); MakeLine(temp[cnt],temp[1]); } for(int i = 1; i <= lines; ++i) line[i].Calc(); sort(line + 1,line + lines + 1); cout << fixed << setprecision(3) << HalfplanIntersection() << endl; return 0; }
BZOJ 2618 CQOI 2006 凸多边形 半平面交
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。