cf 782b

这个题的写法有两种一种是对于时间二分，一种是对于那个相遇的坐标二分，两种做法都有尝试

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 下面先贴，关于时间的二分的做法

#include <iostream> #include <cstdio> #include <cstring> #include <cstdlib> #include <algorithm> #include <vector> #include <map> #include <math.h> #include <stack> #define LL long long using namespace std; const int INF = 0x3f3f3f3f; int dir[4][2] = {{1,0},{0,1},{-1,0},{0,-1}}; const int maxn = 60000 + 10; int k[maxn]; int s[maxn]; int n; bool judge(double t) { double ri,le; ri = k[0] + t * s[0]; le = k[0] - t * s[0]; for(int i = 0; i <n; i++) { //if(i == 0) //{ // ri = k[0] + t * s[0]; // le = k[0] - t * s[0]; //} double ri1 = k[i] + t* s[i]; double le1 = k[i] - t* s[i]; if(ri1 < le || le1 > ri) { return false; } ri = min(ri,ri1); le = max(le,le1); } return true; } int main() { double min_n = INF; double max_n = 0; //double l,r; scanf("%d",&n); for(int i = 0; i < n; i++) { scanf("%d",&k[i]); } for(int i = 0 ; i < n; i++) { scanf("%d",&s[i]); } // cout<<max_n<<" "<<min_n<<endl; double l = 0,r = 1e9; while(r - l > 1e-6) { double mid = (r+l) / 2; if(judge(mid)) { r = mid; } else l = mid; } printf("%.7lf",r); return 0; }再贴关于距离二分的做法

#include <iostream> #include <cstdio> #include <cstring> #include <cstdlib> #include <algorithm> #include <vector> #include <map> #include <math.h> #include <stack> #define LL long long using namespace std; const int INF = 0x3f3f3f3f; int dir[4][2] = {{1,0},{0,1},{-1,0},{0,-1}}; const int maxn = 60000 + 10; double k[maxn]; double s[maxn]; int main() { int n; double min_n = INF; double max_n = 0; //double l,r; scanf("%d",&n); for(int i = 0; i < n; i++) { scanf("%lf",&k[i]); min_n = min(min_n,k[i]); max_n = max(max_n,k[i]); } for(int i = 0 ; i < n; i++) { scanf("%lf",&s[i]); } // cout<<max_n<<" "<<min_n<<endl; double cur = INF; while(min_n <= max_n) { double mid = (min_n + max_n)/2,x; double sum = 0; for(int i = 0; i < n; i++) { double a = fabs(k[i] - mid) / s[i]; if(sum < a) { sum = a; x = k[i]; } } //cout<<x<<endl; //cout<<cur<<endl; cur = min(sum,cur); if(mid <= x) { min_n = mid + 0.000001; } else { max_n = mid - 0.000001; } } printf("%lf\n",cur); return 0; } 这两种二分的方法都可以，以后想问题的方法还是要多元化一点