首页 > 代码库 > 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;}