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個(gè)人的位子，以及N個(gè)人的速度，最終希望這些人都匯聚到一個(gè)點(diǎn)上，問(wèn)最短時(shí)間，地點(diǎn)任選。
思路：
1、聽(tīng)說(shuō)三分最終匯聚的地點(diǎn)也是可以做的。
2、考慮最終解時(shí)間，隨著時(shí)間的增加，匯聚到一點(diǎn)上的可能就越大，那么這里包含一個(gè)單調(diào)性，我們可以二分最終時(shí)間。
那么首先我們對(duì)所有人的位子按照從小到大排序。
對(duì)于當(dāng)前二分出來(lái)的時(shí)間mid，求出每個(gè)點(diǎn)能夠走到的最左邊位子l【i】，以及能夠走到的最右邊的位子r【i】.
我們進(jìn)行判斷，如果出現(xiàn)了max（l【i】）>min（r【i】）的情況，那么肯定所有人就都能匯聚到一點(diǎn)了。
如果可以匯聚到一點(diǎn)，減小時(shí)間，否則增大時(shí)間。
過(guò)程維護(hù)最終解即可。
3、關(guān)于精度的確定問(wèn)題，在這場(chǎng)比賽中學(xué)會(huì)了一個(gè)小技巧，卡二分次數(shù)。
我們可以考慮最大二分次數(shù)來(lái)代替精度問(wèn)題。
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);    }}