poj 1755 Triathlon(半平面交解不等式)

发布时间:2016-12-8 14:04:21 编辑:www.fx114.net 分享查询网我要评论
本篇文章主要介绍了"poj 1755 Triathlon(半平面交解不等式)",主要涉及到poj 1755 Triathlon(半平面交解不等式)方面的内容,对于poj 1755 Triathlon(半平面交解不等式)感兴趣的同学可以参考一下。

n个人参加铁人三项的比赛,给出他们每一项的速度u,v,w,裁判可以决定每一项的距离,问是否存在一种安排,使得这个人能够赢。 对于每个人,如果存在安排的方法就输出Yes,没有就输出No。 这里可以假设三段路程分别为x,y,z,则有:t = x/u+y/v+z/w,这里可以把其中一段路程看成是1,假设把z看作1,则t=x/u+y/v+1/w,如果第一个人要赢,则t1-ti<0,变下不等号的方向则是:ti-t1>0,x/ui+y/vi+1/wi-x/u1+y/vi+1/w1>0,等价于: x*(u1-ui)/(u1*ui)+y*(v1-vi)/(v1*vi)+(w1-wi)/(w1*wi)>0,接下来就是利用半平面交解这些不等式组了,初始先定义一个范围(0,0)(0,INF)(INF,INF)(INF,0),在这个范围内求解半平面交,如果存在就表示能赢,反之,则不能赢。这里利用面积来判断是否存在半平面交后的多边形。 开始精度用的1e-8WA了,看了discus后改成1e-16就过了。。。 #include<iostream> #include<cstdio> #include<string.h> #include<algorithm> #include<math.h> #include<queue> #include<stack> #include<map> #include<vector> #define mm(a,b) memset(a,b,sizeof(a)) #define maxn 305 using namespace std; const int inf=0x7ffffff; const double PI=acos(-1.0); const double eps=1e-16; const double e=2.7182818284590452354; struct node { double u,v,w; }num[maxn]; struct point { double x,y; point() {} point(double x,double y): x(x),y(y) {} }p[maxn],q[maxn],pnt[maxn]; int cnt,curcnt,n; void initial() { p[1]=point(0,0); p[2]=point(inf,0); p[3]=point(inf,inf); p[4]=point(0,inf); p[5]=p[1]; p[0]=p[4]; cnt=4; } 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); return point((v*x.x+u*y.x)/(u+v),(v*x.y+u*y.y)/(u+v)); } void cut(double a,double b,double c) { curcnt=0; for(int i=1;i<=cnt;i++) { if(a*p[i].x+b*p[i].y+c>0) q[++curcnt]=p[i]; else { if(a*p[i-1].x+b*p[i-1].y+c>0) q[++curcnt]=intersect(p[i],p[i-1],a,b,c); if(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]=p[1]; p[0]=p[curcnt]; cnt=curcnt; } double getarea(point pp[],int m) { double area=0; for(int i=1;i<=m;i++) area+=pp[i].x*pp[i+1].y-pp[i+1].x*pp[i].y; return fabs(area*0.5); } bool solve(int id,int n) { initial(); double a,b,c; for(int i=1;i<=n;i++) { if(i==id) continue; a=(num[id].u-num[i].u)/(num[id].u*num[i].u); b=(num[id].v-num[i].v)/(num[id].v*num[i].v); c=(num[id].w-num[i].w)/(num[id].w*num[i].w); if(a==0 && b==0 && c<=eps) return 0; cut(a,b,c); } if(getarea(p,cnt)<eps) return 0; else return 1; } int main() { int n; while(~scanf("%d",&n)) { for(int i=1;i<=n;i++) scanf("%lf%lf%lf",&num[i].u,&num[i].v,&num[i].w); for(int i=1;i<=n;i++) { if(solve(i,n)) puts("Yes"); else puts("No"); } } return 0; }

上一篇:Letter Combinations of a Phone Number
下一篇:DialogResult

相关文章

相关评论