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;
}
参考文献:
[1] https://yhx-12243.github.io/OI-transit/records/cf832C.html