首页 > 代码库 > POJ 1279
POJ 1279
发现好多半平面交用N^2的增量法都能过诶。。。
#include <iostream>#include <cstdio>#include <cstring>#include <algorithm>#include <cmath>using namespace std;const int MAXN=1550;const double eps=1e-8;struct point { double x,y;};point pts[MAXN],p[MAXN],q[MAXN];int ansCnt,curCnt,n;double DB(double d){ if(d>eps) return 1; if(d<-eps) return -1; return 0;}double getArea(point *tmp,int n){ double ans=0; for(int i=1;i<=n;i++) ans+=(tmp[i].x*tmp[i+1].y-tmp[i+1].x*tmp[i].y); return ans/2;}void Adjust(){ for(int i=1;i<(n+1)/2;i++) swap(pts[i],pts[n-i]);}void initial(){ double area=getArea(pts,n); if(DB(area)>=0) Adjust(); for(int i=1;i<=n;i++) p[i]=pts[i]; p[n+1]=p[1]; p[0]=p[n]; ansCnt=n;}void getline(point x,point y,double &a,double &b,double &c){ a=y.y-x.y; b=x.x-y.x; c=x.y*y.x-x.x*y.y;}point intersect(point x,point y,double a,double b,double c){ double u=fabs(a*x.x+b*x.y+c); double v=fabs(a*y.x+b*y.y+c); point pt; pt.x=(x.x*v+y.x*u)/(u+v); pt.y=(x.y*v+y.y*u)/(u+v); return pt;}void cut(double a,double b,double c){ curCnt=0; for(int i=1;i<=ansCnt;i++){ if(DB(a*p[i].x+b*p[i].y+c)>=0) q[++curCnt]=p[i]; else { if(DB(a*p[i-1].x+b*p[i-1].y+c)>0) q[++curCnt]=intersect(p[i],p[i-1],a,b,c); if(DB(a*p[i+1].x+b*p[i+1].y+c)>0) q[++curCnt]=intersect(p[i],p[i+1],a,b,c); } } for(int i=1;i<=curCnt;i++){ p[i]=q[i]; } ansCnt=curCnt; p[ansCnt+1]=p[1]; p[0]=p[ansCnt];}void slove(){ initial(); for(int i=1;i<=n;i++){ double a,b,c; getline(pts[i],pts[i+1],a,b,c); cut(a,b,c); }}int main(){ int cas=0; int t; scanf("%d",&t); while(t--){ scanf("%d\n",&n); cas++; for(int i=1;i<=n;i++) scanf("%lf%lf",&pts[i].x,&pts[i].y); pts[n+1]=pts[1]; slove(); double as=getArea(p,ansCnt); printf("%.2lf\n",fabs(as)); } return 0;}
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。