Codeforces 782B The Meeting Place Cannot Be Changed(二分答案)

题目链接 The Meeting Place Cannot Be Changed

二分答案即可。

check的时候先算出每个点可到达的范围的区间，然后求并集。判断一下是否满足l <= r就好了。

eps我设了1e-7。

 1 #include <bits/stdc++.h>
 2 
 3 using namespace std;
 4 
 5 #define rep(i, a, b)              for(int i(a); i <= (b); ++i)
 6 
 7 const int N      =    100000      +       10;
 8 const double eps =    1e-7;
 9 
10 double mi, ma;
11 
12 struct node{
13     double x, y;
14     friend bool operator < (const node &a, const node &b){
15         return a.x < b.x;
16     }
17 }a[N];
18 int n;
19 
20 double c[N], d[N];
21 
22 bool check(double x){
23     rep(i, 1, n){
24         c[i] = a[i].x - a[i].y * x;
25         d[i] = a[i].x + a[i].y * x;
26     }
27 
28     double l = c[1], r = d[1];
29     rep(i, 2, n){
30         l = max(l, c[i]);
31         r = min(r, d[i]);
32     }
33 
34     return l <= r;
35 }
36 
37 int main(){
38 
39     mi = 2e9, ma = -mi;
40     scanf("%d", &n);
41     rep(i, 1, n){
42         scanf("%lf", &a[i].x);
43         mi = min(mi, a[i].x);
44         ma = max(ma, a[i].x);
45     }
46 
47     rep(i, 1, n){
48         scanf("%lf", &a[i].y);
49     }
50 
51     sort(a + 1, a + n + 1);
52 
53     double l = 0, r = 1000000000;
54     while (abs(l - r) > eps){
55 
56         double mid = (l + r) / 2;
57 
58         if (check(mid)) r = mid; else l = mid;
59     }
60         
61     printf("%.10f
", l);
62     return 0;
63 
64 }