B. The Meeting Place Cannot Be Changed
Description
The main road in Bytecity is a straight line from south to north. Conveniently, there are coordinates measured in meters from the southernmost building in north direction.
At some points on the road there are n friends, and i-th of them is standing at the point xi meters and can move with any speed no greater than vi meters per second in any of the two directions along the road: south or north.
You are to compute the minimum time needed to gather all the n friends at some point on the road. Note that the point they meet at doesn’t need to have integer coordinate.
The first line contains single integer n (2 ≤ n ≤ 60 000) — the number of friends.
The second line contains n integers x1, x2, ..., xn(1≤xi≤109)— the current coordinates of the friends, in meters.
The third line contains n integers v1, v2, ..., vn(1≤vi≤109)— the maximum speeds of the friends, in meters per second.
Output
PRint the minimum time (in seconds) needed for all the n friends to meet at some point on the road.
Your answer will be considered correct, if its absolute or relative error isn’t greater than 10 - 6. Formally, let your answer be a, while jury’s answer be b. Your answer will be considered correct if ∣a−b∣max(1,b)≤10−6 holds.
题意
在一维坐标轴上，有 n 个点 xi，每个点的最大移动速度为 vi 。问最短多少时间可以使得 n 个点在同一个位置相遇。
分析
读完题目就可以大致考虑通过二分枚举最短时间 t 来解决此题。
对于每个枚举的时间 t ，O(N) 处理每个点所能到达的最左最右区间，比较 n 个点的区间交是否存在即可。
代码
#include<bits/stdc++.h>using namespace std;const int N = 60000 + 10;const double eps = 1e-6;int n, x[N], v[N];bool jud(double t){ double l = 0, r = 10e9; for(int i=1;i<=n;i++) { l = max(l, x[i]-v[i]*t); r = min(r, x[i]+v[i]*t); if(l>r) return false; } return true;}double solve(){ double l = 0, r = 1e9, mid, ans; while(r-l>eps) { mid = (l+r)/2.0; if(jud(mid)) r = mid - eps, ans = r; else l = mid + eps; } return ans;}int main(){ scanf("%d",&n); for(int i=1;i<=n;i++) scanf("%d",&x[i]); for(int i=1;i<=n;i++) scanf("%d",&v[i]); printf("%.10lf/n",solve());}
