## 题目描述

$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$.

## 代码

#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;
}


418 I'm a teapot