题解 P5485 【[JLOI2010]铁人双项比赛】

· · 题解

并不会半平面交。

考虑二分答案ans,即第一名领先第二名的时间。

首先将速度的单位从km/h转换为km/s,然后我们可以处理出每跑1千米n号选手领先i号选手的时间为t1_i,每骑1千米n号选手领先i号选手的时间为t2_i(t1_i和t2_i均可为负,负值表示n号选手落后于i号选手)。

对于二分的答案ans，对于所有的i(1\le i<n)要求n号选手领先i号选手不少于ans秒，则可以得出n-1个关于k的不等式:

k\times t1_i + (s - k) \times t2_i \ge ans k \times (t1_i - t2_i) \ge ans - s \times t2_i

只有k是未知数，可以对于t1_i - t2_i的正负分情况讨论解出k的范围:

当t1_i - t2_i < 0时，k \le \frac{ans - s \times t2_i}{t1_i - t2_i}

当t1_i - t2_i = 0时，ans - s \times t2_i \le 0若不成立，则此ans不合法。

当t1_i - t2_i > 0时，k \ge \frac{ans - s \times t2_i}{t1_i - t2_i}

若k有解，则此ans合法，否则此ans不合法。

题面并没有说，但是应该是在有多种方案时输出k最小的方案，所以最后利用二分出的答案解出k的范围，输出的时候用k的下界输出。

#include<cstdio>
#include<cctype>
#include<algorithm>
using namespace std;
int read()
{
    int x = 0;
    int f = 1;
    char ch = getchar();
    for(;!isdigit(ch);ch = getchar())
        if(ch == '-')
            f = -1;
    for(;isdigit(ch);ch = getchar())
        x = x * 10 + (ch ^ 48);
    return x * f;
}
void print(int x)
{
    if(x < 0)
        putchar('-'),x = -x;
    char ch = x % 10 + '0';
    if(x > 9)
        print(x / 10);
    putchar(ch);
}
const int N = 150;
double t1[N],t2[N],s;
int n;
bool check(double ans)
{
    double maxx = s,minn = 0;
    for(int i = 1;i < n;i++)
    {
        double l = t1[i] - t2[i],r = ans - s * t2[i];
        if(t1[i] == t2[i])
            if(r > 0)
                return false;
        if(t1[i]  > t2[i])
            minn = max(minn,r / l);
        if(t1[i] < t2[i])
            maxx = min(maxx,r / l);
    }
    return maxx > minn;
}
void P(double ans)
{
    double minn = 0;
    for(int i = 1;i < n;i++)
    {
        double l = t1[i] - t2[i],r = ans - s * t2[i];
        if(t1[i]  > t2[i])
            minn = max(minn,r / l);
    }
    printf("%.2lf %.2lf %.0lf\n",minn,s - minn,ans);
}
int main()
{
    freopen("1.in","r",stdin);
    s = read(),n = read();
    for(int i = 1;i <= n;i++)
    {
        scanf("%lf %lf",&t1[i],&t2[i]);
        t1[i] = 3600 / t1[i],t2[i] = 3600 / t2[i];
    }
    for(int i = 1;i < n;i++)
        t1[i] -= t1[n],t2[i] -= t2[n];
    double l = -1,r = 1e50;
    while(r - l >= 0.01)
    {
        double mid = (l + r) / 2;
        if(check(mid))
            l = mid;
        else
            r = mid;
    }
    if(r < 0)
        puts("NO");
    else
        P(r);
}