首页 > 代码库 > POJ 1755

POJ 1755

列出不等式后,把同时除Z把它去掉。

注意了,这里应该 是把直线变两点表示的向量更为简单,我开始就直接用直线写,后来,唉,写不下去了。。

#include <iostream>#include <algorithm>#include <cstdio>#include <cmath>using namespace std;const int MAX=110;const double eps=1e-10;const double inf=1e10;struct point{	double x,y;};point operator -(point x,point y){	point t;	t.x=x.x-y.x; t.y=x.y-y.y;	return t;}double operator *(point x,point y){	return x.x*y.y-x.y*y.x;}struct line{	point a,b;	double angle;};int n,lnum;double A[MAX],B[MAX],C[MAX];line le[MAX],st[MAX];int DB(double d){	if(fabs(d)<eps) return 0;	if(d>0) return 1;	return -1;}void addLine(double x1,double y1,double x2,double y2){	point a; a.x=x1; a.y=y1;	point b; b.x=x2; b.y=y2;	le[lnum].a=a; le[lnum].b=b;	le[lnum].angle=atan2(y2-y1,x2-x1);}bool cmp( line x, line y){	if(fabs(x.angle-y.angle)<eps){		if((y.b-x.a)*(x.b-y.a)>eps)		return true;		return false;	}	return x.angle<y.angle;	}void getIntersect(line l1, line l2, point& p) {      double dot1,dot2;      dot1 = (l1.b-l2.a)*(l1.a-l2.a);      dot2 = (l2.b-l1.b)*( l1.a-l1.b);      p.x = (l2.a.x * dot2 + l2.b.x * dot1) / (dot2 + dot1);      p.y = (l2.a.y * dot2 + l2.b.y * dot1) / (dot2 + dot1);  }      bool judge(line l0, line l1, line l2) {      point p;      getIntersect(l1, l2, p);      return DB((l0.a-p)*(l0.b-p)) <=0;   }bool pare(line x,line y){	return fabs((x.b-x.a)*(y.b-y.a))<eps;}bool half(){	int top=1,bot=0;	sort(le,le+lnum,cmp);	int tmp=1;	for(int i=1;i<lnum;i++){		if(fabs(le[i].angle-le[tmp-1].angle)>eps) le[tmp++]=le[i];	}	lnum=tmp;	st[0]=le[0]; st[1]=le[1];	for(int i=2;i<lnum;i++){		while(bot<top&&judge(le[i], st[top-1], st[top])) top--;		while(bot<top&&judge(le[i],st[bot+1],st[bot])) bot++;		st[++top]=le[i];	}	while(bot<top&&judge(st[bot],st[top-1],st[top])) top--;	while(bot<top&&judge(st[top],st[bot+1],st[bot])) bot++;	if(top<=bot+1) return false;	return true;}bool slove(int s){	int i, j, k;    double x1, y1, x2, y2, a, b, c;  	lnum=0; 	addLine(0, 0, inf, 0 );   lnum++;    addLine(inf, 0, inf, inf );  lnum++;    addLine(inf, inf, 0, inf );  lnum++;    addLine(0, inf, 0, 0 );  lnum++;       for (j = 0; j < n; j++)      	if (s != j) {  			a = 1.0 / A[j] - 1.0 / A[s];     			b = 1.0 / B[j] - 1.0 / B[s];        		c = 1.0 / C[j] - 1.0 / C[s];          	int d1 = DB(a);           	int d2 = DB(b);            	int d3 = DB(c);              	if (!d1) {              	if (!d2) {               		if (d3 <= 0) {                 			return false;                    	}                     	continue;               	}                  x1 = 0;                  x2 = d2;                  y1 = y2 = - c / b;               }               else {               	if (!d2) {                		x1 = x2 = - c / a;                  	y1 = 0;                      y2 = -d1;                   }                   else {                   	x1 = 0; y1 = - c / b;                    	x2 = d2;                     	y2 = -(c + a * x2) / b;                   }               }               addLine(x1, y1, x2, y2 );             lnum++;	}  	if(!half()) return false;	return true;}int main(){	while(scanf("%d",&n)!=EOF){		for(int i=0;i<n;i++)		scanf("%lf%lf%lf",&A[i],&B[i],&C[i]);		for(int i=0;i<n;i++){			if(slove(i)) printf("Yes\n");			else printf("No\n");		}	}	return 0;}