题解 CF739E【Gosha is hunting】

0x3F · 2023-07-23 22:51:15 · 题解

这是一种我口胡的 wqs 二分的新的实现方法。

假设我们要最小化答案（虽然这道题不是），wqs 二分，就是你要求一个下凸包上 x=x_0 位置的值，但是你不能直接求，你唯一可以做的事是求凸包与斜率为 k 的直线的切点。

一般的 wqs 二分的思路是：根据这个切点的 x 坐标是大了还是小了，来调整 k 的值。这样有一个问题：如果凸包上有三点共线，那么切点的位置不是唯一的。一维的情况下，可以只选取 x 坐标最小/最大的切点，而二维的情况下，重合的可能是一个平面，所以不能这么做。

那么怎么办呢？

考虑这条切线和直线 x=x_0 的交点，这个交点显然是唯一的。它的 y 坐标只可能小于或等于答案，而绝不会大于答案，取等号当且仅当切线恰好经过要求的点。同时，这个交点的 y 坐标关于 k 的函数 y(k) 是上凸的。

见图。

三分 k 求其最大值即可。不如叫 wqs 三分

如果要最大化答案，或者高维的情况，是类似地，就不再赘述了。

这是这道题的代码：

#include <bits/stdc++.h>
using namespace std;
const int _ = 2e3 + 10;
const long double eps = 1e-10L;
int n, a, b;
long double p[_], q[_];
inline long double calcxy(long double x, long double y) {
    long double sum = a * x + b * y;
    for (int i = 1; i <= n; i++) {
        sum += max({0.0L, p[i] - x, q[i] - y, p[i] + q[i] - p[i] * q[i] - x - y});
    }
    return sum;
}
inline long double calcx(long double x) {
    long double l = -1e4L;
    long double r = 1e4L;
    while (r - l > eps) {
        long double m1 = (l * 2 + r) / 3;
        long double m2 = (l + r * 2) / 3;
        if (calcxy(x, m1) > calcxy(x, m2)) {
            l = m1;
        } else {
            r = m2;
        }
    }
    return calcxy(x, (l + r) / 2);
}
inline long double calc(void) {
    long double l = -1e4L;
    long double r = 1e4L;
    while (r - l > eps) {
        long double m1 = (l * 2 + r) / 3;
        long double m2 = (l + r * 2) / 3;
        if (calcx(m1) > calcx(m2)) {
            l = m1;
        } else {
            r = m2;
        }
    }
    return calcx((l + r) / 2);
}
int main() {
    cin >> n >> a >> b;
    for (int i = 1; i <= n; i++) {
        cin >> p[i];
    }
    for (int i = 1; i <= n; i++) {
        cin >> q[i];
    }
    cout << fixed << setprecision(20) << calc() << endl;
    return 0;
}