题解：CF1575M Managing Telephone Poles

tribool4_in · 2024-04-30 21:32:53 · 题解

首先欧氏距离的式子的形式非常像经典斜率优化形式。于是考虑对于某个点 (x,y)，其答案可以表示为 \displaystyle\min_i\{(x-x_i)^2+(y-y_i)^2\}=x^2+y^2+\min_i\{x_i^2+y_i^2-2x_ix-2y_iy\}。

这个式子跟 x,y 均有关，没法直接斜率优化。于是考虑固定 y，点 (x,y) 的答案即 \displaystyle f_y(x)=x^2+y^2+\min_i\{(x_i^2+y_i^2-2y_iy)-2x_i\cdot x\}。这就相当于所有 (2x_i,x_i^2+y_i^2-2y_iy) 构成的下凸壳上，斜率为 k=x 的直线切得的截距。

此时由于需要对于每个 y 进行处理，且每次会处理 O(n^2) 个关键点（假设 n,m 同阶），复杂度为 O(n^3) 仍无优化。

但是考虑当固定 y_0 时，若两个点 i,j 满足 x_i=x_j,|y_i-y_0|<|y_j-y_0|，则对于所有 x 的点 (x,y_0) 到点 i 的距离一定小于点 j。因此只需要对于每个 x 找出同行最近的点加入凸壳即可，这个过程可以 O(n^2) 预处理。于是对于每个 y 只会加入 O(n) 个点，总复杂度 O(n^2\log n)。

#include <bits/stdc++.h>
using namespace std;
const int N = 2e3 + 10;
int n, m;
int pre[N][N], nxt[N][N];
char s[N][N];
struct Point {
    int x, y;
    Point(int _x, int _y) : x(_x), y(_y) {}
    bool operator<(const Point &rhs) const { return x < rhs.x || (x == rhs.x && y < rhs.y); }
};
Point operator-(const Point &a, const Point &b) { return Point(a.x - b.x, a.y - b.y); }
int operator*(const Point &a, const Point &b) { return a.x * b.y - a.y * b.x; }
vector<Point> l, h;
int main() {
    ios::sync_with_stdio(false);
    cin.tie(0), cout.tie(0);
    cin >> n >> m, ++n, ++m;
    for (int i = 1; i <= n; i++) cin >> (s[i] + 1);
    for (int i = 1; i <= n; i++) {
        for (int j = 1, k = 0; j <= m; j++) {
            if (s[i][j] == '1') k = j;
            pre[i][j] = k;
        }
        for (int j = m, k = 0; j >= 1; j--) {
            if (s[i][j] == '1') k = j;
            nxt[i][j] = k;
        }
    }
    long long ans = 0;
    for (int i = 1; i <= m; i++) {
        l.clear(), h.clear();
        for (int j = 1; j <= n; j++) {
            if (!pre[j][i] && !nxt[j][i]) continue;
            int xi = j, yi = 2 * m;
            if (pre[j][i]) yi = abs(pre[j][i] - i) < abs(yi - i) ? pre[j][i] : yi;
            if (nxt[j][i]) yi = abs(nxt[j][i] - i) < abs(yi - i) ? nxt[j][i] : yi;
            assert(yi != 2 * m);
            l.emplace_back(2 * xi, xi * xi + yi * yi - 2 * i * yi);
        }
        sort(l.begin(), l.end());
        int lh = 0;
        for (auto p : l) {
            while (lh > 1 && (p - h[lh - 2]) * (h[lh - 1] - h[lh - 2]) > 0) h.pop_back(), --lh;
            h.push_back(p), ++lh;
        }
        int pt = 0;
        for (int j = 1; j <= n; j++) {
            while (pt < lh - 1 && (h[pt + 1].y - h[pt].y) < j * (h[pt + 1].x - h[pt].x)) ++pt;
            ans += h[pt].y - 1ll * h[pt].x * j + 1ll * j * j + 1ll * i * i;
        }
    }
    cout << ans << '\n';
    return 0;
}