Strange Radiation

题目描述

$n$ people are standing on a coordinate axis in points with positive integer coordinates strictly less than $10^6$. For each person we know in which direction (left or right) he is facing, and his maximum speed.

You can put a bomb in some point with non-negative integer coordinate, and blow it up. At this moment all people will start running with their maximum speed in the direction they are facing. Also, two strange rays will start propagating from the bomb with speed $s$: one to the right, and one to the left. Of course, the speed $s$ is strictly greater than people’s maximum speed.

The rays are strange because if at any moment the position and the direction of movement of some ray and some person coincide, then the speed of the person immediately increases by the speed of the ray.

You need to place the bomb is such a point that the minimum time moment in which there is a person that has run through point $0$, and there is a person that has run through point $10^6$, is as small as possible. In other words, find the minimum time moment $t$ such that there is a point you can place the bomb to so that at time moment $t$ some person has run through $0$, and some person has run through point $10^6$.

题意概述

在一条数轴上有$n$个人，第$i$个人的位置是$x_i$，速度是$v_i$。每个人初始时都面朝数轴正方向或负方向。现在你可以在数轴某一整点上放置一个炸弹。炸弹爆炸后，所有人都会向他当前面朝的方向奔跑。同时，炸弹会从放置点向数轴正负两侧分别发射出一道激光，速度是$s$。当一道激光碰到一个运动方向相同的人时，这个人的速度会立刻加上$s$。求放置炸弹后，至少有一个人到达$0$且至少有一个人到达$10^6$的最小时间。

数据范围：$2 \le n \le 10^5, \ 0 \le x_i \le 10^6, \ 1 \le v_i \lt s \le 10^6$。

算法分析

答案的范围在$0$到$10^6$之间，考虑二分答案。对于一个时间$t$，分别考虑面向负方向和面向正方向的人。对于负方向的情况，如果某个人不用借助激光就能在时间$t$内到达$0$，则直接考虑正方向；如果某个人借助了激光仍无法在时间$t$内到达$0$，则跳过这个人；否则，计算出在这个人到达$0$的情况下炸弹位置的最大值。右边同理，但求的是最小值。这就相当于求出了若干区间，若它们的交为空，则$t$不满足要求。另外还要考虑炸弹的位置比一个面向负方向的人的位置小或比一个面向正方向的人的位置大的情况。

代码

#include <iostream>
#include <cmath>
#include <iomanip>
using namespace std;
const double eps = 1e-10;
long long n, s;
long long x[100001], v[100001], t[100001];
double l, r;
bool check(double p) {
  bool flag1 = false, flag2 = false;
  for (int i = 1; i <= n; ++i)
    if (t[i] == 1 && 1.0 * x[i] / v[i] <= p) flag1 = true;
    else if (t[i] == 2 && (1e6 - x[i]) / v[i] <= p) flag2 = true;
  if (flag1 && flag2) return true;
  if (flag1) {
    for (int i = 1; i <= n; ++i)
      if (t[i] == 2 && (1e6 - x[i]) / (s + v[i]) <= p) return true;
    return false;
  }
  if (flag2) {
    for (int i = 1; i <= n; ++i)
      if (t[i] == 1 && 1.0 * x[i] / (s + v[i]) <= p) return true;
    return false;
  }
  long long before = 0, after = 1e6;
  for (int i = 1; i <= n; ++i)
    if (t[i] == 1 && 1.0 * x[i] / v[i] > p && 1.0 * x[i] / (s + v[i]) <= p) after = min(after, x[i]);
    else if (t[i] == 2 && (1e6 - x[i]) / v[i] > p && (1e6 - x[i]) / (s + v[i]) <= p) before = max(before, x[i]);
  if (before < after) return false;
  long long ma = -1e18, mi = 1e18;
  for (int i = 1; i <= n; ++i)
    if (t[i] == 1 && 1.0 * x[i] / v[i] > p && 1.0 * x[i] / (s + v[i]) <= p)
      ma = max(ma, (long long) floor((x[i] * v[i] + p * (s + v[i]) * (s - v[i])) / s));
    else if (t[i] == 2 && (1e6 - x[i]) / v[i] > p && (1e6 - x[i]) / (s + v[i]) <= p)
      mi = min(mi, (long long) ceil((1e6 * (s - v[i]) + x[i] * v[i] - p * (s + v[i]) * (s - v[i])) / s));
  return mi <= ma;
}
int main()
{
  cin >> n >> s;
  for (int i = 1; i <= n; ++i)
    cin >> x[i] >> v[i] >> t[i];
  l = 0, r = 1e6;
  while (r - l > eps) {
    double mid = (l + r) / 2;
    if (!check(mid)) l = mid; else r = mid;
  }
  cout << setprecision(10) << fixed << l << endl;
  return 0;
}