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, andi-th of them is standing at the point x_i meters and can move with any speed no greater thanv_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.

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.

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 than10^?-?6. Formally, let your answer bea, while jury's answer be b. Your answer will be considered correct if holds.

37 1 31 2 1Output
2.000000000000Input
45 10 3 22 3 2 4Output
1.400000000000Note
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個人的位子，以及N個人的速度，最終希望這些人都匯聚到一個點上，問最短時間，地點任選。
思路：
1、聽說三分最終匯聚的地點也是可以做的。
2、考慮最終解時間，隨著時間的增加，匯聚到一點上的可能就越大，那么這里包含一個單調性，我們可以二分最終時間。
那么首先我們對所有人的位子按照從小到大排序。
對于當前二分出來的時間mid，求出每個點能夠走到的最左邊位子l【i】，以及能夠走到的最右邊的位子r【i】.
我們進行判斷，如果出現了max（l【i】）>min（r【i】）的情況，那么肯定所有人就都能匯聚到一點了。
如果可以匯聚到一點，減小時間，否則增大時間。
過程維護最終解即可。
3、關于精度的確定問題，在這場比賽中學會了一個小技巧，卡二分次數。
我們可以考慮最大二分次數來代替精度問題。
Ac代碼：
#include<stdio.h>#include<string.h>#include<iostream>#include<algorithm>using namespace std;#define eps 1e-6struct node{    double pos,v;}a[600050];double l[600050];double r[600050];double minn[600050];double maxn[600050];int n;int cmp(node a,node b){    return a.pos<b.pos;}int Slove(double mid){    for(int i=0;i<n;i++)    {        l[i]=a[i].pos-mid*a[i].v;        r[i]=a[i].pos+mid*a[i].v;    }    double posl=l[0];    double posr=r[0];    for(int i=1;i<n;i++)    {        posl=max(posl,l[i]);        posr=min(posr,r[i]);        if(posl>posr)return 0;    }    return 1;}int main(){    while(~scanf("%d",&n))    {        for(int i=0;i<n;i++)        {            scanf("%lf",&a[i].pos);        }        for(int i=0;i<n;i++)        {            scanf("%lf",&a[i].v);        }        int cnt=0;        sort(a,a+n,cmp);        double ans=-1;        double l=0;        double r=1000000005;        while(cnt<=150)        {            cnt++;            double mid=(l+r)/2;            if(Slove(mid)==1)            {                r=mid;                ans=mid;            }            else l=mid;        }        printf("%.8lf/n",ans);    }}