题目描述
传送门
题目大意：铁人双项比赛由长跑和骑自行车组成。现在给定总赛程s，以及每个选手长跑和骑车的平均速度，请你求出对于某个指定的选手最有利的k和r。所谓最有利，是指选择了这个k和r后，该选手可以获得冠军，且领先第2名尽量地多。
题解
这道题刚开始的想法是解不等式组，然后得到一个k的范围，再确定最优解。 但是发现就算解出了范围，也不满足什么单调性。所以就考虑别的了。 对于每个选手其实，都可以用一条直线表示k与时间t的关系。
t=(1v1−1v2)k+sv2
如果我们对于1..n-1这些直线求交点，那么最优解一定出现在交点中。那么相当于用n所在的直线去卡这些交点求最优值。 其实就是一个线性规划问题。 数据范围比较小直接暴力就可以了。 感觉貌似可以求出交点在再求凸包，然后直接判断凸包上的点。 好像也可以用半平面交直接求交点，然后判断。
代码
#include<cstdio>
#include<cmath>
#include<algorithm>
#include<iostream>
#define N 1003
using namespace std;
int n;
double s,a[N],b[N],ans,pos;
void solve(
double x)
{
if (x<
0||x>s)
return;
double ti=
1e13;
for (
int i=
1;i<n;i++)
ti=min(ti,a[i]*x+b[i]);
ti-=a[n]*x+b[n];
if (ti>ans) ans=ti,pos=x;
}
int main()
{
freopen(
"a.in",
"r",stdin);
scanf(
"%lf%d",&s,&n);
for (
int i=
1;i<=n;i++) {
double x,y;
scanf(
"%lf%lf",&x,&y);
a[i]=
1.0/x-
1.0/y;
b[i]=s/y;
}
ans=-
1e13;
for (
int i=
1;i<n;i++)
for (
int j=i+
1;j<n;j++)
solve((b[j]-b[i])/(a[i]-a[j]));
solve(
0.0); solve(s);
if (ans>=
0)
printf(
"%.2lf %.2lf %.0lf\n",pos,s-pos,ans*
3600);
else printf(
"NO\n");
}
