题意：
现在有n个选手和长度为s的赛道；
现要将赛道分为前后两段，前半段长度为k；
第i个选手在前半段的速度是v1,后半段的速度是v2；
求一种对第n个选手最有利的一个k，使其领先第二名尽可能多；
如果他不可能第一，输出NO；
题解：列出第i个选手到终点的时间ti=k/v1i+(n-k)/v2i；
化简ti=(1/v1i-1/v2i)*k+n/v2i；
设k为x轴，时间为y轴，那么这时一条直线；
我们对前n-1名选手的直线求半平面交，得到对每个k，n-1个人中谁最快；
而对于第n名选手，最优的k一定在这个凸包与直线斜率相切的时候；
我们二分出这个位置，，然后求出所有选手在这个k下的时间与选手n的作比较；
然后判断输出即可，注意最优的k可能为负，这时要将其调整为0；
代码：
#include<math.h>#include<stdio.h>#include<iomanip>#include<string.h>#include<iostream>#include<algorithm>#define N 110using namespace std;typedef long double ld;ld v1[N],v2[N];struct Point{ld x,y;Point(){}Point(ld _,ld __):x(_),y(__){}friend Point operator +(Point a,Point b){return Point(a.x+b.x,a.y+b.y);}friend Point operator -(Point a,Point b){return Point(a.x-b.x,a.y-b.y);}friend Point operator *(ld a,Point b){return Point(a*b.x,a*b.y);}friend ld operator ^(Point a,Point b){return a.x*b.y-a.y*b.x;}}p[N];struct Line{Point p,v;ld alpha;Line(){}Line(Point _,Point __){p=_,v=__,alpha=atan2(v.y,v.x);}friend bool operator <(Line a,Line b){return a.alpha<b.alpha;}ld operator [](ld x){return (p+x*v).y;}friend bool Onleft(Line a,Point b){return (a.v^b-a.p)>0;}friend Point getP (Line a,Line b){Point u=a.p-b.p;ld temp=(b.v^u)/(a.v^b.v);return a.p+temp*a.v;}}l[N],q[N];int st,en;void HPI(int n){int i;q[st=en=1]=l[1];for(i=2;i<=n;i++){while(st<en&&Onleft(l[i],p[en]))en–;if(fabs(l[i].alpha-q[en].alpha)<1e-6)q[en]=Onleft(l[i],q[en].p)?q[en]:l[i];elseq[++en]=l[i];p[en]=getP(q[en-1],q[en]);}}int main(){int n,i,j,k;ld s,ans;cin>>s>>n;for(i=1;i<=n;i++){cin>>v1[i]>>v2[i];l[i]=Line(Point(0,s/v2[i]),Point(1,1/v1[i]-1/v2[i]));}sort(l+1,l+n);HPI(n-1);k=lower_bound(q+st,q+en+1,l[n])-q;p[k].x=min(s,max((ld)0,p[k].x));for(i=1,ans=1e100;i<n;i++){ans=min(ans,l[i][p[k].x]-l[n][p[k].x]);}if(ans>=0)cout<<fixed<<setprecision(2)<<p[k].x<<' '<<s-p[k].x<<' ',cout<<fixed<<setprecision(0)<<ans*60*60<<endl;elseputs("NO");return 0;}
没有什么可凭仗，只有他的好身体，没有地方可去，只想到处流浪。
