2021牛客暑期多校训练营5 F、Finding Points

题目大意

按逆时针给出凸包上的个点，你要在凸包里面找到一个点，让的最小值最大，然后输出这个最大的最小值。

Solution

考点：三分

比较明显的容易发现如果我们固定，那么的相关函数一定是一个单峰函数。

同理固定，那么的相关函数也一定是单峰函数。

那么就直接用三分套三分就可以求解了，复杂度。

const int INF = 0x3f3f3f3f;
const int N = 100 + 7;
const double PI = acos(-1);
ll n, m;
pai p[N];

double xmax = -INF, xmin = INF, ymax = -INF, ymin = INF;

pai operator - (const pai& a, const pai& b) {
    return { a.first - b.first,a.second - b.second };
}

double operator * (const pai& a, const pai& b) {
    return a.first * b.first + a.second * b.second;
}

double getLen(pai a) {
    return sqrt(a * a);
}

double getAngle(pai a, pai b) {
    return acos(a * b / getLen(a) / getLen(b));
}

double check(pai x) {
    double res = INF;
    for (int i = 1; i <= n; ++i) {
        res = min(res, getAngle(p[i] - x, p[i + 1] - x));
    }
    return res;
}

double calc(double x) {
    double l = ymin, r = ymax;
    for (int i = 1; i <= 100; ++i) {
        double lmid = l + (r - l) / 3.0;
        double rmid = r - (r - l) / 3.0;
        if (check({ x,lmid }) > check({ x,rmid })) {
            r = rmid;
        }
        else {
            l = lmid;
        }
    }
    return check({ x,l });
}

int solve() {
    n = read();
    for (int i = 1; i <= n; ++i) {
        auto& [x, y] = p[i];
        x = read(), y = read();
        xmax = max(xmax, x);
        xmin = min(xmin, x);
        ymax = max(ymax, y);
        ymin = min(ymin, y);
    }
    p[n + 1] = p[1];

    double l = xmin, r = xmax;

    for (int i = 1; i <= 100; ++i) {
        double lmid = l + (r - l) / 3.0;
        double rmid = r - (r - l) / 3.0;
        if (calc(lmid) > calc(rmid)) {
            r = rmid;
        }
        else {
            l = lmid;
        }
    }

    printf("%.12f\n", calc(l) * 180 / PI);


    return 1;
}