hubeikemi的个人博客
0%

浮点二分和三分

发表于 分类于
本文字数： 3.8k 阅读时长 ≈ 3 分钟

https://ac.nowcoder.com/acm/contest/120454/F

属于典型的“是否存在一个 X ∈ R 可以满足所有约束”的问题

浮点二分

二分解法： 二分答案$r^2$，然后将区间$x-\sqrt{r^2-y^2}$到$x+\sqrt{r^2-y^2}$ 区间覆盖判断，若所有区间存在交集，则返回true

先看错解：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
#include<bits/stdc++.h>
using namespace std;
struct node {
    double x, y;
};
 
void solve(){
 
    int n; cin >> n;
    vector<node> a(n + 1);
    for (int i = 1; i <= n; ++i) {
        cin >> a[i].x >> a[i].y;
    }
    auto check = [&](double R2) -> bool {
        double L = -1e9, R = 1e9;
        for (int i = 1; i <= n; ++i) {
            double X = R2 - a[i].y * a[i].y;
            double l = a[i].x - sqrt(X);
            double r = a[i].x + sqrt(X);
            L = max(L, l);
            R = min(R, r);
        }
        return L <= R;
    };
    double l = -1e9, r = 1e9;
    double ans;
    while (l <= r) {
        double mid = l + (r - l) / 2.0;
        if (check (mid)) {
            ans = mid;
            l = mid + 1;
        }
        else {
            r = mid - 1;
        }
    }
    cout << sqrt(ans) << endl;
 
}
 
int main(){
 
    ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    int _=1;
    while(_--)
    solve();
    return 0;
 
}

错误点：

  • 在二分一个 double，却使用了整数二分写法 

    1
    2
    3
    4
    5
    while (l <= r) {
        mid = l + (r - l) / 2;
        if (check(mid)) l = mid + 1;
        else r = mid - 1;
    }

    使用这种比较完全不收敛，
    而且 mid + 1 会跳过正确答案，导致永远不精确。

  • check(R2) 没有边界判断

    如果 $r^2$ < $y^2$，$x^2$为负，会 sqrt(负数) → nan → WA/RE

  • 二分区间不应该是 [-1e9, 1e9]

    [-1e9, 1e9] 有一半是无效区间
    因为我们二分答案 $r^2$ ，而半径平方不能为负

正确写法：浮点二分（模板）

1
2
3
4
5
6
7
double l = 0, r = 2e8;   // 1e4^2 + 1e4^2
for (int i = 0; i < 60; i++) {
    double mid = (l + r) / 2;
    if (check(mid)) r = mid;
    else l = mid;
}

不能用 while(l <= r)！！

最终无 bug 版本

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
#include<bits/stdc++.h>
using namespace std;
struct node {
    double x, y;
};
 
void solve(){
 
    int n; cin >> n;
    vector<node> a(n + 1);
    for (int i = 1; i <= n; ++i) {
        cin >> a[i].x >> a[i].y;
    }
    auto check = [&](double R2) -> bool {
        double L = -1e9, R = 1e9;
        for (int i = 1; i <= n; ++i) {
            double X = R2 - a[i].y * a[i].y;

            if (X < 0) return 0;	//若圆与x轴无交点，即X < 0，直接返回false，否则sqrt(X)会nan
            
            double l = a[i].x - sqrt(X);
            double r = a[i].x + sqrt(X);
            L = max(L, l);
            R = min(R, r);
        }
        return L <= R;
    };
    
    double l = 0, r = 1e9;
    for (int i = 1; i <= 60; ++i) {
        double mid = l + (r - l) / 2;
        if (check(mid)) {
            r = mid;	//这里应该以r为答案，之前连这里都错了！
        }
        else {
            l = mid;
        }
    }
    
    cout << setprecision(6) << sqrt(r) << endl;
 
}
 
int main(){
 
    ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    int _=1;
    while(_--)
    solve();
    return 0;
 
}

三分

三分法是一种用于在“单峰/单谷函数f(x)”上寻找最优值（最大或最小）的算法。

三分法思想：

把区间 [l, r] 分成三段： l —— m1 —— m2 —— r

其中： m1 = l + (r - l) / 3 （左三等分点）
m2 = r - (r - l) / 3（右三等分点）

然后比较： f(m1) 和 f(m2)

如果 f(m1) < f(m2)
→ 最高点在区间 (m1, r)
→ 扔掉左边部分 l = m1

如果 f(m1) > f(m2)
→ 最高点在区间 (l, m2)
→ 扔掉右边部分 r = m2

三分法代码模板（整数区间）

1
2
3
4
5
6
7
8
9
10
11
12
int ternary(int l, int r) {
    while (r - l >= 3) {
        int m1 = l + (r - l) / 3;
        int m2 = r - (r - l) / 3;

        if (f(m1) < f(m2)) 
            l = m1;
        else 
            r = m2;
    }
}

三分法代码模板（实数区间）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
double ternary(double l, double r) {
    const double eps = 1e-12; 

    while (r - l > eps) {
        double m1 = l + (r - l) / 3;
        double m2 = r - (r - l) / 3;

        if (f(m1) < f(m2)) {
            l = m1;
        } else {
            r = m2;
        }
    }
}

算了，直接看题吧

我们要在 x 轴上选一个点 X，使得到所有点 ($x_i$, $y_i$) 的 最大距离最小：

$f(x) = \max\limits_{1 \le i \le n}\sqrt{(X - x_i)^2 + y_i^2}$

自己感受一下：$X$从x轴左边到x轴右边，$\max\limits_{1 \le i \le n}\sqrt{(X - x_i)^2 + y_i^2}$ 肯定先变小后变大

所以这个函数 是凹的（单峰），我们要搜$f(x)$ 的最小值（对应$x$为X），因此可用 三分法 搜索 X。

代码（AC 版本，C++）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
#include<bits/stdc++.h>
using namespace std;

struct node {
    int x, y;
};

void solve(){
    
    int n; cin >> n;
    vector<node> a(n + 1);
    for (int i = 1; i <= n; ++i) {
        cin >> a[i].x >> a[i].y;
    }

    auto f = [&](double x) -> double {
        double mx = 0;
        for (int i = 1; i <= n; ++i) {
            double dx = a[i].x - x, dy = a[i].y;
            mx = max(mx, sqrt(dx * dx + dy * dy));
        }
        return mx;
    };

    double l = -10000, r = 10000;
    for (int i = 1; i <= 60; ++i) {
        double m1 = l + (r - l) / 3;
        double m2 = r - (r - l) / 3;
        if (f(m1) > f(m2)) {
            l = m1;
        }
        else {
            r = m2;
        }
    }

    cout << setprecision(6) << f((l + r) / 2.0) << endl;
    
}
    
int main(){

    ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    int _=1;
    while(_--)
    solve();
    return 0;
    
}

收工！