簡易題敘#
有 \(n\) ( \(1 \le n \le 10^5\) ) 個人，每個人都有自己的位置 \(x_i\) ( \(-10^9 \le x_i \le 10^9\) ) 跟移動速度 \(v_i\) ( \(1 \le v_i \le 10^9\) ) ，求所有人相聚的最短時間。輸出答案跟正確答案誤差要小於 \(-10^6\)。
範例測資：
- 輸入
5
-1 5
10 3
4 2
7 10
8 1
- 輸出
1.5
概念講解#
這題看起來沒辦法直接算出時間，但一定存在某個時間 ( 本題所求：集合所需最少時間 )，在他之前都集合不了，在他之後都可以集合，這意味著我們可以用二分搜的方式，找到那個至少可以集合所有人的時間，搜個 100 次就很夠了 ( \(2^{100} > 10^{31}\) )。
check函式的功能，就是檢測現在這個時間夠不夠大家集合。因為在一定時間內，人可以向左走或向右走，所以其實可以把這段時間內人能到的地方用線段表示，這樣一來要求的就是這個重疊線段存不存在。設 \(mx\)、 \(mn\) 分別是目前所有線段左界的最大值跟右界的最小值 ( 你可以把它當成重疊線段左右界 )，如果 \(mx \le mn\)，代表現在所有線段有共同交集，答案存在；否則，如果 \(mx\) 超過 \(mn\)，就代表有某個線段的左界超過目前答案的右界，也就是他們不可能重疊，沒有大家都重疊的線段，那就說明不可能在這個時間內集合所有人。
範例程式碼#
#include <bits/stdc++.h>
using namespace std;
#define int long long
const int N = 1e5 + 5;
int n, x[N], v[N], cnt = 100;
bool check(double t) {
double mx = -1e10, mn = 1e10;
for (int i = 0; i < n; i++) {
mx = max(mx, x[i] - t * v[i]);
mn = min(mn, x[i] + t * v[i]);
if (mx > mn) {
return 0;
}
}
return 1;
}
signed main() {
cin >> n;
for (int i = 0; i < n; i++) {
cin >> x[i] >> v[i];
}
double l = -0.1, r = 1e9 + 0.1; // 左開右開，避免沒檢查到 0 秒跟 1e9 秒
while (cnt--) {
double mid = (l + r) / 2;
if (!check(mid)) l = mid;
else r = mid;
}
cout << fixed << setprecision(8) << r << '\n';
return 0;
}
