poj1755 Triathlon 半平面交
题目链接：http://poj.org/problem?id=1755
题目意思：给出N个运动员的游泳，骑车，跑步的三个速度u,v,w，问对于每一个运动员可不可以在比赛中获得第一名。
解题思路：刚开始一看到这题根本不懂要干什么，最后才知道要求半平面交。
令总路程为S，三个运动的路程的比例为X ：Y : 1-X-Y;要在比赛中获胜的条件是在相同路程下的时间用得最短。对于运动员i与另外的运动员j相比，
X/ui+Y/vi+(1-X-Y)/wi < X/uj+Y/vj+(1-X-Y)/wj（同时除以S后），根据这个进行求平面交，其中可行区域的初始值为 x>=0,y>=0 x+y<=1;构成了一个三角形区域。
代码如下：47MS AC
#include<iostream>#include<cstdio>#include<cstring>#include<cmath>#define eps 1e-16using namespace std;const int MAXN=105;struct point{double x,y;};struct node{double a ,b ,c;};point points[MAXN*2],p[MAXN*2],q[MAXN*2];node nodes[MAXN];int cnt,temp;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 ret; ret.x=(x.x * v + y.x * u) / (u + v); ret.y=(x.y * v + y.y * u) / (u + v); return ret; } void slove(double a,double b,double c){temp=0;int i;for(i=0;i<cnt;i++){if(a*p[i].x+b*p[i].y+c>=0)q[temp++]=p[i];else{if(a*p[(i+cnt-1)%cnt].x+b*p[(i+cnt-1)%cnt].y+c>0)q[temp++]=intersect(p[i],p[(i+cnt-1)%cnt],a,b,c);if(a*p[(i+1)%cnt].x+b*p[(i+1)%cnt].y+c>0)q[temp++]=intersect(p[i],p[(i+1)%cnt],a,b,c);}}cnt=temp;for(i=0;i<temp;i++)p[i]=q[i];}double area(point p[],int n){double res=0;int i;for(i=0;i<n;i++)res+=p[(i+1)%n].x*p[i].y-p[i].x*p[(i+1)%n].y;return fabs(res)/2.0;}int main(){int n;while(scanf("%d",&n)!=EOF){int i,j;for(i=0;i<n;i++){scanf("%lf%lf%lf",&nodes[i].a,&nodes[i].b,&nodes[i].c);}points[0].x=0,points[0].y=0;points[1].x=0,points[1].y=1;points[2].x=1,points[2].y=0;for(i=0;i<n;i++){cnt=3;memcpy(p,points,sizeof(points[0])*3);bool iswin=false;for(j=0;j<n;j++)if(i!=j){if(nodes[i].a<=nodes[j].a&&nodes[i].b<=nodes[j].b&&nodes[i].c<=nodes[j].c)break;double aa,bb,cc;cc=1/nodes[i].c-1/nodes[j].c;aa=1/nodes[i].a-1/nodes[j].a-cc;bb=1/nodes[i].b-1/nodes[j].b-cc;slove(-aa,-bb,-cc);}if(j!=n||cnt<3)printf("No\n");else{double res=area(p,cnt);if(fabs(res)<eps)printf("No\n");else printf("Yes\n");}}}return 0;}