Online Judge | Problem Set | Authors | Online Contests | User | ||||||
---|---|---|---|---|---|---|---|---|---|---|
Web Board Home Page F.A.Qs Statistical Charts | Current Contest Past Contests Scheduled Contests Award Contest |
用Zzy方法(nlog(n))过,注意eps至少要去1e-10/* 题意:给出一些向量,求出围成的多边形的核的面积 朱泽圆专为他那篇nlog(n)算法解决半平面交问题的论文而出的题目,至今不会自己写(汗颜,自己全是套模板). */ #include<iostream> #include<queue> #include<cstdio> #include<algorithm> #include<cstring> #include<iomanip> #include<map> #include<cstdlib> #include<cmath> #include<vector> #define LL long long #define IT __int64 #define zero(x) fabs(x)<eps #define mm(a,b) memset(a,b,sizeof(a)) const int INF=0x7fffffff; const double inf=1e8; const double eps=1e-10; const double PI=acos(-1.0); const int Max=20001; using namespace std; struct point { double x; double y; }p[Max]; struct Segment { point s; point e; double angle; void get_angle() { angle=atan2(e.y-s.y,e.x-s.x);//得到斜率对应的角度 } }seg[Max]; int m; //叉积为正说明,p2在p0-p1的左侧 double xmul(point p0,point p1,point p2) { return (p1.x-p0.x)*(p2.y-p0.y)-(p2.x-p0.x)*(p1.y-p0.y); } point Get_Intersect(Segment s1,Segment s2)//求交点 { double u,v; u=xmul(s1.s,s1.e,s2.s); v=xmul(s1.e,s1.s,s2.e); point res; res.x=(s2.s.x*v+s2.e.x*u)/(u+v); res.y=(s2.s.y*v+s2.e.y*u)/(u+v); return res; } bool cmp(Segment s1,Segment s2) { if(s1.angle>s2.angle) //先按极角排序 return true; else if(zero(s1.angle-s2.angle)&&xmul(s2.s,s2.e,s1.e)>-eps) //极角相等,内侧的在前 return true; return false; } void initial()//初始化 { seg[0].s.x=0; seg[0].s.y=0; seg[0].e.x=10000; seg[0].e.y=0; seg[0].get_angle(); seg[1].s.x=10000; seg[1].s.y=0; seg[1].e.x=10000; seg[1].e.y=10000; seg[1].get_angle(); seg[2].s.x=10000; seg[2].s.y=10000; seg[2].e.x=0; seg[2].e.y=10000; seg[2].get_angle(); seg[3].s.x=0; seg[3].s.y=10000; seg[3].e.x=0; seg[3].e.y=0; seg[3].get_angle(); } void HalfPlaneIntersect(Segment seg[],int n)//半平面交模版(nlog(n)) { sort(seg,seg+n,cmp); int temp=1; for(int i=1; i<n; i++) { if(!zero(seg[i].angle-seg[temp-1].angle)) seg[temp++]=seg[i]; } n=temp; Segment deq[Max]; deq[0]=seg[0]; deq[1]=seg[1]; int head=0,tail=1; for(int i=2; i<n; i++) { while(head<tail&&xmul(seg[i].s,seg[i].e,Get_Intersect(deq[tail],deq[tail-1]))<-eps) tail--; while(head<tail&&xmul(seg[i].s,seg[i].e,Get_Intersect(deq[head],deq[head+1]))<-eps) head++; deq[++tail]=seg[i]; } while(head<tail&&xmul(deq[head].s,deq[head].e,Get_Intersect(deq[tail],deq[tail-1]))<-eps) tail--; while(head<tail&&xmul(deq[tail].s,deq[tail].e,Get_Intersect(deq[head],deq[head+1]))<-eps) head++; if(head==tail) return; m=0; for(int i=head; i<tail; i++) p[m++]=Get_Intersect(deq[i],deq[i+1]); if(tail>head+1) p[m++]=Get_Intersect(deq[head],deq[tail]); } double Get_area(point p[],int &n)//叉积求多边形面积 { double area=0; for(int i=1; i<n-1; i++) area+=xmul(p[0],p[i],p[i+1]); return fabs(area)/2.0; } int main() { int n; while(scanf("%d",&n)!=EOF) { initial();//初始化 for(int i=4; i<n+4; i++) { scanf("%lf%lf%lf%lf",&seg[i].s.x,&seg[i].s.y,&seg[i].e.x,&seg[i].e.y); //cin>>seg[i].s.x>>seg[i].s.y>>seg[i].e.x>>seg[i].e.y; seg[i].get_angle(); } HalfPlaneIntersect(seg,n+4); printf("%.1lf\n",Get_area(p,m)); //cout<<setprecision(1)<<setiosflags(ios::fixed)<<Get_area(p,m)<<endl; } return 0; } Followed by: Post your reply here: |
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator