题目
https://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=2674
题意
有严格下降的n条线段，长度都为w，第i条线段起点xi，终点xi + w，高度yi，现在有s种垂直恒定速度可以选择，水平速度不能超过vh，问要经过每条线段，垂直恒定速度最大可以选择什么
思路
明显，二分枚举速度speed
第一条线段因为是起点所以肯定都能到达
对于第i条线段，从第i-1条线段出发落到i条线段相同高度所用时间为t = (yi - y_{i - 1}) / speed，设能到达的区域为[xlefttruei, xrighttruei]，能到达的区域为[xlefttrue_{i-1}- vh * t, xrighttrue_{i-1} + vh * t]与自身线段[xi, xi + w]的交集，如果不存在这个交集，就代表落不到这个线段上。
感想：
现在uva无法通过，包括他人题解注明已通过的也不行
代码
#include <algorithm>
#include <cassert>
#include <cmath>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <map>
#include <queue>
#include <set>
#include <string>
#include <tuple>
#define LOCAL_DEBUG
using namespace std;
const int MAXN = 1e5 + ;
const int MAXS = 1e6 + ;
long long xleft[MAXN];
long long y[MAXN];
long long w, vh;
int n, s;
long long xlefttrue[MAXN], xrighttrue[MAXN];
int speeds[MAXS];
bool check(int speed) {
xlefttrue[] = xleft[] * speed;
xrighttrue[] = (xleft[] + w) * speed;
for (int i = ; i < n; i++) {
long long t = (y[i] - y[i - ]);
xlefttrue[i] = max(xleft[i] * speed, xlefttrue[i - ] - t * vh);
xrighttrue[i] = min((xleft[i] + w) * speed, xrighttrue[i - ] + t * vh);
if (xlefttrue[i] > xrighttrue[i])return false;
}
return true;
} int main() {
#ifdef LOCAL_DEBUG
freopen("C:\\Users\\Iris\\source\\repos\\ACM\\ACM\\input.txt", "r", stdin);
//freopen("C:\\Users\\Iris\\source\\repos\\ACM\\ACM\\output.txt", "w", stdout);
#endif // LOCAL_DEBUG
int T;
cin >> T;
for (int ti = ;ti <= T; ti++) {
cin >> w >> vh >> n;
for (int i = ; i < n; i++) {
cin >> xleft[i] >> y[i];
}
cin >> s;
for (int i = ; i < s; i++) {
cin >> speeds[i];
}
sort(speeds, speeds + s);
int lind = , rind = s;
if (!check(speeds[lind]))cout << "IMPOSSIBLE" <<endl;
else {
while (lind < rind) {
int mid = (lind + rind) >> ;
if (mid == lind)break;
if (check(speeds[mid])) {
lind = mid;
}
else {
rind = mid;
}
}
cout << speeds[lind] << endl;
}
} return ;
}