[BZOJ2756][JLOI2010]铁人双项比赛（半平面交+三分法）

题目描述

传送门

题目大意：n个人参加比赛，先跑步和自行车的总路程为s，其中跑步为k，走路为r，每个人跑步和自行车都有一个速度。求出对第n个人最有利的k和r，使其获得冠军，并且领先第二名的时间最多。

题解

首先将每个人的k-时间方程写出来 y=x/v1+(s-x)/v2=(1/v1-1/v2)x+s/v2 这样得到了n个方程，用半平面交求凸壳（其它比半平面交高明到不知道哪里去了的办法都资瓷 求出凸壳之后判断第n条直线是否在凸壳上有位置（有一个点也包括），如果有的话，就得到了一个合法的区间，直观观察可以发现和第二名的差距在区间上是单峰的，可以三分求解

代码

#include<algorithm> #include<iostream> #include<cstring> #include<cstdio> #include<cmath> using namespace std; #define N 105 const double eps=1e-9; const double inf=1e9; int dcmp(double x) { if (x<=eps&&x>=-eps) return 0; return (x>0)?1:-1; } struct Vector { double x,y; Vector(double X=0,double Y=0) { x=X,y=Y; } }; typedef Vector Point; struct Line { double k,b; Point p,q; Line(double K=0,double B=0) { k=K,b=B; } }; Vector operator + (Vector a,Vector b){return Vector(a.x+b.x,a.y+b.y);} Vector operator - (Vector a,Vector b){return Vector(a.x-b.x,a.y-b.y);} Vector operator * (Vector a,double b){return Vector(a.x*b,a.y*b);} int n,cnt; double s; Line line[N]; Point poly[N],npoly[N]; double Cross(Vector a,Vector b){return a.x*b.y-a.y*b.x;} bool ins(Point A,Point B,Point C,Point D) { Vector v,u,w; v=B-A,u=C-A,w=D-A; if (dcmp(Cross(v,u))==dcmp(Cross(v,w))) return 0; v=D-C,u=A-C,w=B-C; if (dcmp(Cross(v,u))==dcmp(Cross(v,w))) return 0; return 1; } Point GLI(Point P,Vector v,Point Q,Vector w) { Vector u=P-Q; double t=Cross(w,u)/Cross(v,w); return P+v*t; } void init() { cnt=0; poly[++cnt]=Point(0,0); poly[++cnt]=Point(0,inf); poly[++cnt]=Point(s,inf); poly[++cnt]=Point(s,0); } void halfp(Point A,Point B) { Point C,D;int ncnt=0; for (int i=1;i<=cnt;++i) { C=poly[i]; D=poly[i%cnt+1]; if (dcmp(Cross(C-A,B-A))>=0) npoly[++ncnt]=C; if (ins(A,B,C,D)) npoly[++ncnt]=GLI(A,B-A,C,D-C); } cnt=ncnt; for (int i=1;i<=cnt;++i) poly[i]=npoly[i]; } double check(double x) { double Min=inf; for (int i=1;i<n;++i) Min=min(Min,line[i].k*x+line[i].b); return Min-(line[n].k*x+line[n].b); } double find(double l,double r) { double mid1,mid2,ans1,ans2,ans; while (r-l>eps) { mid1=l+(r-l)/3.0; mid2=r-(r-l)/3.0; ans1=check(mid1); ans2=check(mid2); if (ans1>=ans2) ans=mid1,r=mid2; else ans=mid2,l=mid1; } return ans; } int main() { scanf("%lf%d",&s,&n); for (int i=1;i<=n;++i) { double v1,v2;scanf("%lf%lf",&v1,&v2); line[i]=Line(1/v1-1/v2,s/v2); line[i].p.x=0,line[i].p.y=line[i].b; line[i].q.x=s,line[i].q.y=line[i].k*s+line[i].b; } init(); for (int i=1;i<=n;++i) halfp(line[i].p,line[i].q); bool flag=0;double ans; for (int i=1;i<=cnt;++i) { double xa=poly[i].x,ya=poly[i].y,xb=poly[i%cnt+1].x,yb=poly[i%cnt+1].y; if (!dcmp(xa-xb)||(!dcmp(ya)&&!dcmp(yb))) continue; double know=(ya-yb)/(xa-xb); double bnow=ya-xa*know; if (!dcmp(line[n].k-know)&&!dcmp(line[n].b-bnow)) { flag=1; ans=find(poly[i].x,poly[i%cnt+1].x); break; } } if (!flag) { for (int i=1;i<=cnt;++i) if (!dcmp(line[n].k*poly[i].x+line[n].b-poly[i].y)) { flag=1; ans=poly[i].x; break; } if (!flag) puts("NO"); else printf("%.2lf %.2lf %.0lf\n",ans,s-ans,check(ans)*3600+eps); } else printf("%.2lf %.2lf %.0lf\n",ans,s-ans,check(ans)*3600+eps); }