CodeForces - 782BThe Meeting Place Cannot Be Changed

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 x_i meters and can move with any speed no greater than v_i 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.

Input

The first line contains single integer n (2 ≤ n ≤ 60 000) — the number of friends.

The second line contains n integers x₁, x₂, ..., x_n (1 ≤ x_i ≤ 10⁹) — the current coordinates of the friends, in meters.

The third line contains n integers v₁, v₂, ..., v_n (1 ≤ v_i ≤ 10⁹) — 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  holds.

Example Input 3 7 1 3 1 2 1 Output 2.000000000000 Input 4 5 10 3 2 2 3 2 4 Output 1.400000000000 Note

In the first sample, all friends can gather at the point 5 within 2 seconds. In order to achieve this, the first friend should go south all the time at his maximum speed, while the second and the third friends should go north at their maximum speeds.

题目大意：

  一条线上的不同位置分别站了n个人，这些人的速度为v【i】，现在让你找出一个点，使得这些人以他们的最大速度到达这个点所需时间最短。

题目分析：

  一个二分问题，二分的是时间，首先取这些人两个相距最远的中点，计算他们每个人到达这个位置的时间，中点左边的人的所用的最长时间和中点右边的人所用的最长时间比较，如果差距在0.0000001即可认为满足要求，倘若差距大，就移动中点。。。直到差距在0.0000001。。。代码刚开始的如果r和l和mx和mn的反掉了，所以一直没有输出结果，改正后就行了。。。二分这个是重点要关注的。

#include <cstdio> #include <cstring> #include <iostream> #include <algorithm> #include <cmath> using namespace std; const int maxn = 60005; double x[maxn]; double v[maxn]; int main(){ int n; while((scanf("%d",&n))!=EOF){ double mx=0,mn=0; for(int i=1;i<=n;i++) cin>>x[i], mx=max(mx,x[i]), mn=min(mn,x[i]); for(int i=1;i<=n;i++) cin>>v[i]; double r=1,l=0; while(fabs(r-l) >= 0.0000001){//r为那一点左边的人到达那一点所需要的最长时间，l相似。 double mid=(mx+mn)/2.0; r=l=0; for(int i=1;i<=n;i++){ if(x[i] > mid) r = max(r,(x[i]-mid)/v[i]); if(x[i] <= mid) l = max(l, (mid-x[i])/v[i]); } if(r > l) mn=mid; if(r == l) break; if(r < l) mx= mid; } printf("%.7lf",r); } return 0; }