ACM - CF1059D 二分/三分

题目链接

题意：
n个点，给定（Xi，Yi）的坐标，问：找到一个最小半径的圆，既与x轴相切，又包含所有的n个点。

边界条件：
当n个点，既有出现在x轴上方的，又有出现在x轴下方的点时，不存在。
当n个点，出现了至少两个点在x轴上时，不存在。
画画图就能想明白。
圆需要与x轴相切，必然与x轴只有1个交点。

二分做法：

给定r，判断是否可行。

代码

#include <bits/stdc++.h>
using namespace std;

const int maxn = 1e5 + 20;
int n;
double x[maxn];
double y[maxn];

int ok(double r){
    double xleft = -1e15, xright = 1e15, tmp;
    for(int i = 1; i <= n; i++){
        if (y[i] > 2 * r) return 0;
        tmp = sqrt(2 * r * y[i] - y[i] * y[i]);
        xleft = max(xleft, x[i] - tmp);
        xright = min(xright, x[i] + tmp);
    }
    return xleft <= xright;
}

int main(){
    int xcnt = 0;
    int yup = 0;
    int ydown = 0;
    scanf("%d", &n);
    for(int i = 1; i <= n; i++){
        scanf("%lf%lf", &x[i], &y[i]);
        if (y[i] == 0) xcnt ++;
        if (y[i] > 0) yup = 1;
        if (y[i] < 0) ydown = 1, y[i] = - y[i];
    }
    if ((yup && ydown) || (xcnt >= 2))
        printf("-1\n");
    //if (yup && ydown) printf("-1\n");
    else{
        int cnt = 100;
        double l = 0, r = 1e15, mid, ans;
        while(cnt --){
            mid = (l + r) / 2.0;
            if (ok(mid)){
                ans = mid;
                r = mid;
            }
            else l = mid;
        }
        printf("%.6lf\n", ans);
    }
    return 0;
}

着重想讲一讲三分
二分：处理的是单调性问题。能够找到边界值。最大，最小。在[L,R]区间内，函数是单调的。有些值，ok；有些值不ok。
三分：可以处理的是带有一个拐点的问题。能够找到极值。极大或极小。在[L,R]区间内，函数有极值。在极值两侧，单调性相反。
本题中，假设圆心坐标为（x，r），即有：
(x - xi) ^ 2 + (r - yi) ^ 2 = r ^ 2
得到：r = ((x - xi) ^ 2 + yi ^ 2) / (2 * yi)
那么有R = max(r1, r2, ..., rn)
考虑x往-inf，和inf两侧，即x正负半轴走，R都是变大的。
即存在一个极值X0，有左边递减，右边递增，故可以三分。

#include <bits/stdc++.h>
using namespace std;

const int maxn = 1e5 + 20;
int n;
double x[maxn];
double y[maxn];

double calc(double xx){
    double r = 0;
    for(int i = 1; i <= n; i++)
        r = max(r, ((xx - x[i]) * (xx - x[i]) + y[i] * y[i]) / (2.0 * y[i]));
    return r;
}

int main(){
    int xcnt = 0;
    int yup = 0;
    int ydown = 0;
    scanf("%d", &n);
    for(int i = 1; i <= n; i++){
        scanf("%lf%lf", &x[i], &y[i]);
        if (y[i] == 0) xcnt ++;
        if (y[i] > 0) yup = 1;
        if (y[i] < 0) ydown = 1, y[i] = - y[i];
    }
    if ((yup && ydown) || (xcnt >= 2))
        printf("-1\n");
    //if (yup && ydown) printf("-1\n");
    else{
        int cnt = 100;
        double l = -1e7, r = 1e7, dx, ml, mr;
        while(cnt --){
            dx = (r - l) / 3.0;
            ml = l + dx;
            mr = r - dx;
            if (calc(ml) < calc(mr)) r = mr;
            else l = ml;
        }
        printf("%.6lf\n", calc(r));
    }
    return 0;
}