題目鏈接：http://poj.org/problem?id=1755
如何確定兩個平面的交線，題意：一段距離總長度為L,將L分成三部分a,b和c(a、b、c均大于0)。有N(1?<=?N?<=?100)?個人，第i個人在這三段中的速度分別是Vi,Ui和Wi(1?<=?Vi,?Ui,?Wi?<=?10000)?。問是否存在一種分法，使得第i個人可以成為冠軍（并列冠軍不算，也就是只有i一個人是冠軍）。
思路：對于某種分法，第i個人用的時間ti=a/Vi+b/Ui+c/Wi,第j個人用的時間tj=a/Vj+b/Uj+c/Wj,那么本題的要求就是對于i（1<=i<=N),是否有可能對于所有的j（1<=j<=N?且j!=i），滿足ti-tj<0?即（1/Vi-1/Vj）*a+(1/Ui-1/Uj)*b+(1/Wi-1/Wj)*c<0 。兩邊同時除以c得（令X=a/c,Y=b/c，A=1/Vi-1/Vj，B=1/Ui-1/Uj，C=1/Wi-1/Wj):A*X+B*Y+C<0。到此，可以看出，就是一個半平面求交的問題。然后每個人用其他人交一下，求出最后的面積，大于0即可。我們注意到X=a/c>=0,Y=b/c>=0(其實嚴格按照題意來說是大于0),X+Y=(a+b)/c=(L-c)/c=L/c-1，因此初始化時必然是一頂點在原點且在第一象限的等腰三角形。至于這個等腰三角形的兩個腰長是多少為保險起見建議定的大一點，我是定的100000。
?
int DB(double x)
{if(x>1e-25) return 1;if(x<-1e-25) return -1;return 0;
}struct point
{double x,y;point(){}point(double _x,double _y){x=_x;y=_y;}void read(){RD(x,y);}void output(){printf("(%.2lf %.2lf)",x,y);}point operator+(point a){return point(x+a.x,y+a.y);}point operator-(point a){return point(x-a.x,y-a.y);}double operator*(point a){return x*a.y-y*a.x;}point operator*(double t){return point(x*t,y*t);}point operator/(double t){return point(x/t,y/t);}bool operator==(point a){return DB(x-a.x)==0&&DB(y-a.y)==0;}bool operator!=(point a){return DB(x-a.x)||DB(y-a.y);}
};struct line
{double a,b,c;line(){}line(double _a,double _b,double _c){a=_a;b=_b;c=_c;}line(point p,point q){a=q.y-p.y;b=p.x-q.x;c=p.y*q.x-p.x*q.y;}
};point a[N];
int n;//t在ab的左側返回正值
double cross(point a,point b,point t)
{return point(b-a)*point(t-a);
}point getCross(point a,point b,point p,point q)
{double s1=(a-p)*(b-p);double s2=(b-q)*(a-q);double t=s1+s2;return (p*s2+q*s1)/(s1+s2);
}point getCross(line L1,line L2)
{point p;p.x=(L2.c*L1.b-L1.c*L2.b)/(L1.a*L2.b-L2.a*L1.b);if(DB(L2.b)) p.y=-(L2.a*p.x+L2.c)/L2.b;else p.y=-(L1.a*p.x+L1.c)/L1.b;return p;
}double getDist(point a,point b)
{return sqrt(sqr(a.x-b.x)+sqr(a.y-b.y));
}double getArea(point p[],int n)
{double ans=0;int i;p[n]=p[0];FOR0(i,n) ans+=p[i]*p[i+1];return ans/2;
}void moveSegment(point &p1,point &p2,double r)
{r/=getDist(p1,p2);point p=point(p1.y-p2.y,p2.x-p1.x)*r;p1=p1+p;p2=p2+p;
}int m,V[N],U[N],W[N];double cal(double A,double B,double C,point a)
{return A*a.x+B*a.y+C;
}void cut(point a[],int &n,double A,double B,double C)
{if(!n) return;point b[N],p;int i,m=n,t1,t2;FOR0(i,n) b[i]=a[i];b[n]=b[0];n=0;FOR0(i,m){t1=DB(cal(A,B,C,b[i]));t2=DB(cal(A,B,C,b[i+1]));p=getCross(line(A,B,C),line(b[i],b[i+1]));if(!t1&&t2<0||t1<0&&t2<0||t1<0&&!t2||!t1&&!t2){a[n++]=b[i];a[n++]=b[i+1];}else if(t1>0&&!t2) a[n++]=b[i+1];else if(t1>0&&t2<0) a[n++]=p,a[n++]=b[i+1];else if(t1<0&&t2>0) a[n++]=b[i],a[n++]=p;else if(!t1&&t2>0) a[n++]=b[i];}m=1;FOR1(i,n-1) if(a[i]!=a[i-1]) a[m++]=a[i];if(a[m]==a[0]) m--;n=m;
}int OK(int i,int j)
{return V[i]==V[j]&&U[i]==U[j]&&W[i]==W[j];
}int main()
{RD(m);int i,j,flag;double A,B,C;FOR1(i,m) RD(V[i],U[i],W[i]);FOR1(i,m){a[0]=point(0,0);a[1]=point(100000,0);a[2]=point(0,100000);n=3;flag=0;FOR1(j,m) if(i!=j){if(flag||OK(i,j)){flag=1;continue;}A=1.0/V[i]-1.0/V[j];B=1.0/U[i]-1.0/U[j];C=1.0/W[i]-1.0/W[j];cut(a,n,A,B,C);}if(!flag&&DB(fabs(getArea(a,n)))) puts("Yes");else puts("No");}return 0;
}
