首页 > 代码库 > POJ 3335

POJ 3335

/*半平面交求核心的增量法:假设前N-1个半平面交,对于第N个半平面,只需用它来交前N-1个平面交出的多边形。算法开始时,调整点的方向为顺时针方向,对于是否为顺时针,只需求出其面积,若为正,必为逆时针的。对于每相邻两点求出一条直线,用该直线去交其半平面,并求出交点及判断原多边形点的方位。*/ #include <iostream>#include <cstdio>#include <cstring>#include <algorithm>#include <cmath>using namespace std;const int MAXN=110;const double eps=1e-8;struct point {	double x,y;};point pts[MAXN],p[MAXN],q[MAXN];int n,cCnt,curCnt;int 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].y*tmp[i+1].x);	return ans/2;}void Adjust(point *ps,int n){	for(int i = 1; i < (n+1)/2; i ++) 	swap(ps[i], ps[n-i]);}void initial(){	double area=getArea(pts,n);	if(DB(area)==1) Adjust(pts,n);	for(int i=1;i<=n;i++)	p[i]=pts[i];	p[n+1]=p[1];	p[0]=p[n];	cCnt=n;}void getline(point x,point y,double &a,double &b,double &c){    a = y.y - x.y;    b = x.x - y.x;    c = y.x * x.y - 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<=cCnt;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];    p[curCnt+1] = q[1];p[0] = p[curCnt];    cCnt = curCnt;}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 t;	scanf("%d",&t);	while(t--){		scanf("%d",&n);		for(int i=1;i<=n;i++)		scanf("%lf%lf",&pts[i].x,&pts[i].y);		pts[n+1]=pts[1];		slove();		if(cCnt>=1) printf("YES\n");		else printf("NO\n");	}	return 0;}