首页 > 代码库 > POJ 1474

POJ 1474

半平面交模板

#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 ansCnt,curCnt,n;double DB(double d){	if(d>eps) return 1;	if(d<-eps) return -1;	return 0;}void initial(){	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;	while(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();		printf("Floor #%d\n",cas);		if(ansCnt>=1)		printf("Surveillance is possible.\n");		else printf("Surveillance is impossible.\n");		printf("\n");	}	return 0;}