Codeforces Round #403 (Div. 2) B. The 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 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.

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.

37 1 31 2 1output
2.000000000000题意：开始每个人都在一条数轴上的某个位置上，位置大于等于1都是整数，每个人有个最大移动速度，为在数轴上面哪个点集合，所用的集合时间最短，
求这个时间，集合地点可以不是整数。
思路：如果路径对短那就是求中位数就好了。但速度不一样，这个点一定是中间某个位置，其它位置都会让结果
变大（为什么会这样，自己手动画画图，把路程线段加和就看出来了）。所以结合点跟集合时间是个有极值的函数。
至于题目中的最大速度，为了时间最少，肯定能多快就多快了，直接用最大速度算。
求极值用三分搜索就可以了，可以算是三分的模板题了。
代码如下：
#include <bits/stdc++.h>const int N = 200010;using namespace std;int x[N], v[N], n;double check(double local){    double ret = 0;    for (int i = 1; i <= n; i++)    {        double a = (double)x[i];        double vt = (double)v[i];        ret = max(ret, fabs(a - local) / vt);    }    return ret;}int main(){#ifndef ONLINE_JUDGE      freopen("in.txt","r" ,stdin);#endif        while (~scanf("%d", &n))    {        int tmp = 0;        for (int i = 1; i <= n; i++)        {            scanf("%d", x + i);            tmp = max(tmp, x[i]);        }        for (int i = 1; i <= n; i++)            scanf("%d", v + i);        double l = 1, r = tmp;        while (r - l > 1e-6)        {            double mid = (l + r)/2;            double midd = (l + mid)/2;            double dt = check(mid);            double ddt = check(midd);            if (dt > ddt)                r = mid;            else                 l = midd;        }        printf("%.8f/n", check(l));    }    return 0;}