题解：P3438 [POI 2006] ZAB-Frogs

首先，如果我们知道每个点到坏点的最小距离是很好做的（二分）。关键在于如何求出:

\min_{i=1}^n{(x-x_i)^2+(y-y_i)^2}

我们对这个式子进行展开:

=x^2+y^2+x_i^2+y_i^2-2y_iy-2x_ix

好像有点像斜率优化？但斜率优化做不了两个变量。考虑固定一个变量。参考扫描线的思路，一层层找，那么 x 就成了已知量。

=(x^2+y^2)-(2y_i)y+(x_i^2+y_i^2-2x_ix)

那么把它看作是一条

k=-2y_i,b=(x_i^2+y_i^2-2x_ix)

的直线。

这个时候有人要问了，每层扫过去重新加线是不是就是

O(nk\log(m))

？

实则不然，注意到

k

只有

m

种，而

k

相等的直线只要保留

b

最小的。

考虑开

m

棵李超线段树。

第

i

棵李超线段树维护

k=-2i

的时候的

b

的最小值。

这样就把预处理写完了。

后面的二分就糖丸了。

CPP

#include <bits/stdc++.h>

using namespace std;
const int N = 1e3 + 5;
int dis[N][N];
struct Node {
    int x, y;
} p[N * N];
struct Line {
    int k, b;
    int val(int x) {return k * x + b;}
    bool empty = 1;
};
struct Seg {
    Line mn;
    int l, r;
    Seg *ls = nullptr, *rs = nullptr;
    void Sg(int x, int y) { l = x, r = y; }
    void ins(Line k) {
        if (mn.empty) mn = k;
        int mid = l + r >> 1;
        bool cmpl = k.val(l) < mn.val(l);
        bool cmpmid = k.val(mid) < mn.val(mid);
        if (cmpmid) swap(k, mn);
        if (l == r) return;
        if (cmpl != cmpmid) {if (!ls) ls = new Seg, ls -> Sg(l, mid); ls -> ins(k);}
        else {if (!rs) rs = new Seg, rs -> Sg(mid + 1, r); rs -> ins(k);}
    }
    int query(int x) {
        int res = 1e9;
        if (!mn.empty) res = mn.val(x);
        int mid = l + r >> 1;
        if (mid >= x && ls) res = min(res, ls -> query(x));
        if (mid < x && rs) res = min(res, rs -> query(x));
        return res; 
    }
    void clear() {
        if (mn.empty == 1) return;
        mn = {0, 0, 1};
        if (ls) ls -> clear();
        if (rs) rs -> clear();
    }
} rt[N];
bool f[N][N], vis[N][N];
int n, m, sx, sy, ex, ey;
queue <Node> q;
int fx[4] = {0, 1, 0, -1};
int fy[4] = {1, 0, -1, 0};
bool check(int k) {
    for (int i = 1 ; i <= n ; i ++)
        for (int j = 1 ; j <= m ; j ++)
            f[i][j] = vis[i][j] = 0;
    vis[sx][sy] = 1;
    while (!q.empty()) q.pop();
    q.push({sx, sy});
    while (!q.empty()) {
        int x = q.front().x, y = q.front().y; q.pop();
        if (x == ex && y == ey) return 1;
        for (int i = 0 ; i < 4 ; i ++) {
            int xx = x + fx[i], yy = y + fy[i];
            if (xx < 1 || xx > n || yy < 1 || yy > m || vis[xx][yy] || dis[xx][yy] < k) continue;
            vis[xx][yy] = 1;
            q.push({xx, yy});
        }
    }
    return 0;
}
signed main() {
    ios::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);
    cin >> n >> m >> sx >> sy >> ex >> ey;
    int k; cin >> k;
    for (int i = 1 ; i <= k ; i ++) cin >> p[i].x >> p[i].y;
    for (int i = 1 ; i <= m ; i ++)
        rt[i].Sg(1, n);
    for (int i = 1 ; i <= k ; i ++) 
        rt[p[i].y].ins({-2 * p[i].x, p[i].x * p[i].x + p[i].y * p[i].y, 0}); // 
    Seg T; T.Sg(1, m);
    for (int i = 1 ; i <= n ; i ++) {
        T.clear();
        for (int j = 1 ; j <= m ; j ++) {
            int b = rt[j].query(i);
            if (b >= 1e9) continue;
            T.ins({-2 * j, b, 0});
        }
        for (int j = 1 ; j <= m ; j ++) 
            dis[i][j] = T.query(j) + i * i + j * j;
    }
    // for (int i = 1 ; i <= n ; i ++, cout << '\n')
    //     for (int j = 1 ; j <= m ; j ++)
    //         cout << dis[i][j] << ' ';
    int l = 0, r = min(dis[sx][sy], dis[ex][ey]);
    while (l < r - 1) {
        int mid = l + r >> 1;
        if (check(mid)) l = mid;
        else r = mid;
    }
    if (check(r)) cout << r;
    else cout << l;
    return 0;
}

说实话比我想得快的多。

题解：P3438 [POI 2006] ZAB-Frogs

文章操作

相关推荐

评论

题解：P3438 [POI 2006] ZAB-Frogs