乱杀
题目描述
乐孤星和 WA90 准备联合参加下一次的 NOB(National Olympiad in Badminton)。
他们想要在一场比赛中击回对手打出的所有球从而赢得比赛，因为 WA90 非常强，所以可以预先知道对手打出的每一个球的位置，他们想要计算一下打败对手需要多认真。
形式化的，我们将羽毛球场比作一个一维数轴，不考虑高度的限制。起初两个人都在数轴的原点，两个人的移动是独立的，并且可以互相越过或处于同一位置。任意时刻，他们可以以不超过 \(V\) 的速度移动或处于静止状态。
现在他们预测到了对手将能打出 \(n\) 次球，第 \(i\) 个球将于时刻 \(t_i\) 飞到位置 \(x_i\)，也就是说在时刻 \(t_i\) 至少有一个人位于 \(x_i\) 才能击回第 \(i\) 个球。现在请你求出两个人若想击回所有的球，速度上限 \(V\) 至少是多少。
输入格式
第一行一个整数 \(n\)。
接下来 \(n\) 行，每行两个整数 \(t\) 和 \(x\)，含义同题目描述。
输出格式
输出两人击回所有球的速度上限 \(V\) 的最小值，你的答案和标准答案误差在 \(10^{-6}\) 以内将视为答案正确。
样例 #1
样例输入 #1
4 1 2 2 4 5 0 6 4样例输出 #1
2.000000000样例 #2
样例输入 #2
3 1 0 3 5 5 0样例输出 #2
1.666666667样例 #3
样例输入 #3
4 1 5 2 -10 4 0 5 -20样例输出 #3
5.000000000提示
「样例解释 #2」
最优的方法是一个人呆在原点，另一个人在 \(3\) 个单位时间之内移动 \(5\) 个单位长度，所以速度至少是 \(\dfrac{5}{3}\)。
「数据范围」
对于全部数据，\(1 \leq n \leq 10^5\)，\(1 \leq t \leq 10^9\)，\(- 10^6 \leq x \leq 10^6\)。
对于任意的 \(i < j\)，保证 \(t_i < t_j\)。
测试点编号 \(n \leq\) \(x \in\) 特殊性质 \(1\) \(15\) \([-10^6,10^6]\) 无 \(2 \sim 3\) \(5 \times 10^2\) \([-10^6,10^6]\) 无 \(4 \sim 7\) \(3 \times 10^3\) \([-10^6,10^6]\) 无 \(8\) \(10^5\) \([0,10^6]\) 有 \(9 \sim 10\) \(10^5\) \([-10^6,10^6]\) 有 \(11 \sim 20\) \(10^5\) \([-10^6,10^6]\) 无
- 特殊性质: 对于任意的 \(i < j\)，有 \(| x_i | \leq | x_j |\)。
-
不错的一道题
-
以下为了方便记 \(f(l,r) = \frac{|x_r-x_l|}{t_r-t_l}\)
-
虽然 \(O(n^2)\) 的做法只能拿到 35 分，但做法是比较典型的。设 \(dp_{i,j}\) 表示打前 \(i\) 个球，一个人在打第 \(i\) 个，另一个人在打第 \(j\) 个的最小的最大速度。
- 然后考虑正解，答案具有单调性显然，故二分答案。
- 显然的，如果能完成 \(x_{i+1}\) 的操作，则 \(x_i\) 上必然有一个人，因此我们只需要考虑如何记录另一个人所在的位置。不妨记 \(x_{i+1}\) 的人为 \(P\) ，另一个人为 \(Q\) 。
- 这里有一个重点：一个人在固定的某一时刻能触碰到的位置一定是一个区间，注意，这里的某一时刻并不指白跑，而是包括击打在这段时间内出现的羽毛球。因此我们用 \([L,R]\) 记录 \(Q\) 这个人所在的位置。令 \(\Delta_t = t_{i+1}-t_i,S=Vt\) ，则 \(P\) 可以到达的区间为 \([x_i - S, x_i + S]\) ， \(Q\) 可以到达 \([L - S, R + S]\)
- 对于一次击球，有四种转移情况：
- 如果这两个区间都不包含 \(x_{i+1}\) ，则无解
- 如果 \(P\) 可以到达而 \(Q\) 不可以，则让 \(L \leftarrow L - S, R \leftarrow R + S\)
- 如果 \(P\) 不能到达而 \(Q\) 可以，则两个人交换身份， \(L \leftarrow X_i - S, R \leftarrow X_i + S\)
- 如果都能到达，则让 \(L,R\) 的取值贪心取最值即可
- 最终复杂度 \(O(n \log A)\)