CF832C Strange Radiation 题解

题意：

$n$ 个人站在一个数轴上，它们的坐标均为正整数，且小于 $10^6$。对于每个人，都有一个面对的方向 (左和右) 以及它的速度。

你可以在一个坐标为非负整数，且不超过 $10^6$ 的位置上放置一个炸弹，并引爆它，这时，所有的人都会按照他们面对的方向以他们的速度跑起来。与此同时，两条奇怪的射线（~~应该是气流吧~~）会以 $v$ 的速度从炸弹的位置发射出来——一条向右、一条向左。当然，速度 $v$ 严格大于人的跑步速度。

这些射线之所以奇怪，是因为如果某一个时刻，射线的位置与某个人的位置重合，且该射线的方向与那个人跑步的方向一致，则他跑步的速度会立即增加射线的速度 $v$。

你需要在一个地方放置一个炸弹，使得目标时间——即有一个人到达过位置 $0$，且还有一个人到达过位置 $10^6$ 的时间——尽可能地小。换句话说，找到最小的时间 $t$，使得存在那么一个放炸弹的位置，使得前 $t$ 个单位时间内有人到达过位置 $0$，且有人到达过位置 $10^6$ （不必同时）。

输入格式：

第一行包含两个正整数 $n, s~(2 \leq n \leq 10^5, ~2 \leq s \leq 10^6)$，表示人的个数和射线的速度。

接下来的 $n$ 行描述每个人。其中第 $i$ 行包含三个正整数 $x_i, v_i, t_i,(0 < x_i < 10^6,~v_i < s,~ t_i \in \{1, 2\})$，分别表示第 $i$ 个人的坐标、他跑步的速度以及他跑步的方向，其中 $1$ 为左（负方向），$2$ 为右（正方向）。

输出格式：

输出目标时间的最小值。你的答案被判定为正确当且仅当绝对误差或相对误差不超过 $10^{-6}$。

目标时间最小值 $t$ ，肯定是考虑二分啦

然后就变成了如何判断是否存在有效的放炸弹的位置

考虑如何检验两边有没有人到达

先考虑某个向左走的人 cxy ，并假设她就是那个先走到 $0$ 的人

则她的坐标 $x_0$ 就是它要走的距离，设她速度为 $v_0$ 。

如果她本来就很快，即 $x_0 \le v_0t$ ，那她根本不用~~吃炸弹灰~~就能跑到

接下来考虑 $x_0 > v_0t$ 。但是我们不知道炸弹在哪里！~~俗话说得好，不知道就设出来~~

设炸弹的位置为 $x$ ，显然有 $x_0 \le x \le 10^6$

然后就是个追及问题

射线追到人的时间为

$t_1=\dfrac{x-x_0}{v-v_0}$

追到的位置为

$\begin{aligned} x_1 &=x-vt_1 \\ &=x-v\dfrac{x-x_0}{v-v_0} \\ &=\dfrac{x_0v-v_0x}{v-v_0} \end{aligned}$

因为 $x_1 \ge 0$ ，所以 $x_0v - v_0x$ ，即

$x \le v\dfrac{x_0}{v_0}$

然后吃到射线后，速度变为 $v_1 = v_0 + v$ ，要走的距离就是

$x_1 = \dfrac{x_0 v - v_0 x}{v-v_0}$

故时间

$t_2 = \dfrac{x_1}{v_1} = \dfrac{x_0v-v_0x}{v^2-v_0^2}$

总时间

$t_{\texttt{总}} = t_1 + t_2 = \dfrac{xv - x_0v_0}{v^2-v_0^2} \le t$

则

$x \le \dfrac{1}{v} \left(x_0v_0 + (v^2-v_0^2)t\right)$

故综上所述

$x_0 \le x \le \min\left\{10^6, ~\dfrac{x_0 v}{v_0},~ \dfrac{1}{v} \left(x_0v_0 + (v^2-v_0^2)t\right)\right\}$

对于每个向左走的人，我们都可以得到一个范围 $l_i \le x \le r_i$ （注意特判空集！）

然后我们取一个并集就好了。对于向右走的人，同样可以推出类似的式子

然后把两个并集求交，如果有交，则有解

判断方法：「两个下界的 $\max$ 」小于等于「两个上界的 $\min$ 」

时间复杂度 $O(-n \log \epsilon)$

代码：

#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cstdarg>
#include <cmath>
#include <iomanip>
#include <random>
using namespace std;
#define int long long
#define double long double
#define INF 0x3f3f3f3f3f3f3f3f
#define N ((int)(1e5+15))

const double Y=1e6;
const double eps=1e-9;

void up(double &x, double y) {x < y ? x = y : 0;}
void down(double &x, double y) {x > y ? x = y : 0;}

int n,x[N],v[N];
bool work(double t)
{
    bool rev=0;
    double v0,x0,l,r;
    double li=Y, ls=0, ri=Y, rs=0;
    for(int i=1; i<=n; i++)
    {
        v0 = (double) ((rev = (v[i] > 0)) ? v[i] : -v[i]);
        x0 = (double) (rev ? Y-x[i] : x[i]);
        if(x0 <= v0 * t) {l=0; r=Y;}
        else
        {
            l=x0; down(r=Y, x0 / v0 * v[0]); // r=min (Y, x0 / v0 * v)
            down(r, (x0 * v0 + ((double) v[0] * v[0] - v0 * v0) * t) / v[0]);
            // x <= (x0 * v0 + (v^2 - v0^2) * t) / v
        }
        if(l > r + eps) continue;
        rev ? down(ri, Y-r) : down(li, l);
        rev ? up(rs, Y-l) : up(ls, r);
    }
    return ceil(max(li,ri)) <= floor(min(ls,rs)) + eps;
}
signed main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    // freopen("check.in","r",stdin);
    // freopen("check.out","w",stdout);
    cout << fixed << setprecision(9);
    cin >> n >> v[0];
    for(int i=1,t; i<=n; i++)
    {
        cin >> x[i] >> v[i] >> t;
        if(t==1) v[i]=-v[i];
    }
    double l=0,r=Y;
    while(r - l > eps)
    {
        double mid=(l + r) * 0.5;
        work(mid) ? r=mid : l=mid;
    }
    cout << (l + r) * 0.5 << '\n';
    return 0;
}