思路:所以选手的时间可以写成 y=kx+b x在这里代表骑行路程。不妨第一名看成是 −y 构成半平面交。求出半平面交的边后,找到由 n 的边,若不是重边,则求出其相邻两条边的交点,以该交点更新答案;否则为并列,更新答案。
#include<bits/stdc++.h>
using namespace std;
const double INF=1E18;
const double pi=acos(-1.0);
const double eps=1e-10;
const int MAX=100+5;
vector<int>g[MAX];
int sgn(double x){
if(fabs(x)<eps)
return 0;
else
return x<0?-1:1;
}
struct Point{
double x,y;
int l1,l2;
Point(){};
Point(double x,double y):x(x),y(y){}
Point operator + (Point B){return Point(x+B.x,y+B.y);}
Point operator - (Point B){return Point(x-B.x,y-B.y);}
Point operator * (double k){return Point(x*k,y*k);}
};
typedef Point Vector;
double Cross(Vector A,Vector B){return A.x*B.y-A.y*B.x;};
struct Line{
Point p;
Vector v;
double ang;
int co;
Line(){};
Line(Point p,Vector v,int co):p(p),v(v),co(co){ang=atan2(v.y,v.x);}
bool operator <(Line &L){return ang<L.ang||sgn(ang-L.ang)==0&&p.y<L.p.y;}
};
bool OnLeft(Line L,Point p){return sgn(Cross(L.v,p-L.p))>=0;}
Point Cross_point(Line a,Line b){
Vector u=a.p-b.p;
double t=Cross(b.v,u)/Cross(a.v,b.v);
return a.p+a.v*t;
}
vector<int> HPI(vector<Line>L){
int n=L.size();
// sort(L.begin(),L.end());
int first,last;
vector<Point> p(n);
vector<Line> q(n);
vector<int> ans;
q[first=last=0]=L[0];
for(int i=1;i<=n-1;++i){
while(first<last&&!OnLeft(L[i],p[last-1])) last--;
while(first<last&&!OnLeft(L[i],p[first])) first++;
q[++last]=L[i];
if(fabs(Cross(q[last].v,q[last-1].v))<eps){
last--;
if(OnLeft(q[last],L[i].p)) q[last]=L[i];
}
if(first<last)
p[last-1]=Cross_point(q[last-1],q[last]);
}
while(first<last&&!OnLeft(q[first],p[last-1])) last--;
for(int i=first;i<=last;++i)
ans.push_back(q[i].co);
return ans;
}
double a[MAX],b[MAX],s;
int main(){
int n;
cin>>s>>n;
vector<Line> L;
vector<Line> tempL;
tempL.push_back(Line(Point(0,0),Vector(0,-1),0));
tempL.push_back(Line(Point(0,INF),Vector(-1,0),n+1));
for(int i=1;i<=n;++i)
scanf("%lf%lf",a+i,b+i);
for(int i=1;i<=n;++i){
tempL.push_back(Line(Point(0,-s/b[i]),Vector(1,-1/a[i]+1/b[i]),i));
}
sort(tempL.begin(),tempL.end());
L.push_back(Line(tempL[0].p,tempL[0].v,0));
int t=0;
g[t].push_back(tempL[0].co);
for(int i=1;i<=n+1;++i){
if(sgn(tempL[i].ang-L[t].ang)==0&&sgn(tempL[i].p.y-L[t].p.y)==0){
g[t].push_back(tempL[i].co);
}
else{
t++;
g[t].push_back(tempL[i].co);
L.push_back(Line(tempL[i].p,tempL[i].v,t));
}
}
vector<int> ans=HPI(L);
double anst;
double ansx=-INF;
double tmin=INF;
for(int i=1;i<=n-1;++i){
tmin=min(tmin,s/b[i]);
}
if(tmin-s/b[n]>ansx){
ansx=tmin-s/b[n];
anst=0;
}
for(int i=1;i<(int)ans.size()-1;++i){
bool flag=0;
for(int j=0;j<g[ans[i]].size();++j){
if(g[ans[i]][j]==n){
flag=1;
break;
}
}
if(flag){
Point p=Cross_point(L[ans[i-1]],L[ans[i+1]]);
if(g[ans[i]].size()==1){
if(p.x<s){
if(ansx<-p.x/a[n]-(s-p.x)/b[n]-p.y){
ansx=-p.x/a[n]-(s-p.x)/b[n]-p.y;
anst=p.x;
}
}
}
else{
if(p.x<s){
if(ansx<0){
ansx=0;
anst=p.x;
}
}
}
}
}
tmin=INF;
for(int i=1;i<=n-1;++i){
tmin=min(tmin,s/a[i]);
}
if(tmin-s/a[n]>ansx){
ansx=tmin-s/a[n];
anst=s;
}
if(ansx>0||sgn(ansx)==0){
cout<<fixed<<setprecision(2)<<anst<<" "<<fixed<<setprecision(2)<<s-anst<<" "<<fixed<<setprecision(0)<<ansx*3600<<endl;
}
else{
cout<<"NO";
}
}