POI2006 ZAB-Frogs

题目:

  一群青蛙正在摧毁Byteotia所有的庄稼. 一个叫Byteasar的农夫决定使用一种放在田里的奇特的"scarefrogs"来吓跑他们, 所有的青蛙在跳跃过程中都尽量使自己离他们越远越好, 即是让自己离最近的scarefrog越远越好. Byteasar的田是块矩形的土地. 青蛙们跳跃的方向平行于坐标轴并且每次跳跃的距离为1. 一条跳跃路线的scarefrogs-距离为路径上所有点距离所有scarefrogs的最近距离. Byteasar已经知道青蛙们的出发位置和目的地位置, 所以他在田里放置了若干个scarefrogs. 他请求你帮忙写一个程序找一条路径使得该路径的scarefrogs-距离最大.

思路:

  如果已知了每个点距离scarefrogs的最近距离,只要二分+bfs就能得到距离的最大值。所以主要问题就是怎么求每个点距离scarefrogs的最近距离。
  设当前要求的点坐标为 ,两个scarefrogs的坐标为 。如果 更近,就能得到这个式子:
  
  稍微变换一下就能得到():
  
  把 看作点对就可以斜率优化了。为了保证 为常数,每次一列一列的计算。显然每一行离当前列最近的才有可以成为最近点,所以每次只会把 个点放入凸包,总的复杂度就是
  如果用桶排代替快排,用并查集代替二分+bfs,复杂度就能达到 (我口胡的没写过代码)

代码:

#include <bits/stdc++.h>
#define mset(a, b) memset(a, b, sizeof a)
#define rep(i, a, b) for(int i(a), i##_END_(b); i <= i##_END_; i++) 
#define drep(i, a, b) for(int i(a), i##_END_(b); i >= i##_END_; i--)
using namespace std;
template<class T> inline bool tomax(T &a, T b) {return a < b ? a = b, 1 : 0;}
template<class T> inline bool tomin(T &a, T b) {return b < a ? a = b, 1 : 0;}
typedef long long ll;
typedef double db;
const int N = 1005, M = N * N;

inline ll P2(int x) { return (ll) x * x; }

int nowx[N], nowa;
ll func(int y) {
    return P2(nowx[y]) - 2ll * nowa * nowx[y] + P2(y);
}
bool check(int a, int b, int c) {
    return (func(a) - func(b)) * (b - c) >= (func(b) - func(c)) * (a - b);
}
int calc(int y, int a, int b) {
    return P2(nowx[y] - a) + P2(y - b);
}

int vec[N][N], con[N], dis[N][N], id[N];
int n, m, p;

void getDis() {
    rep(a, 1, n) {
        nowa = a;
        rep(b, 1, m) {
            int p = lower_bound(vec[b] + 1, vec[b] + 1 + vec[b][0], a) - vec[b];
            nowx[b] = ((vec[b][p] - a) <= (a - vec[b][p - 1]) ? vec[b][p] : vec[b][p - 1]);
        }
        int hed = 1, tai = 0;
        rep(y, 1, m) {
            while(hed < tai && check(con[tai - 1], con[tai], y)) tai--;
            con[++tai] = y;
        }
        rep(b, 1, m) {
            while(hed < tai && calc(con[hed], a, b) >= calc(con[hed + 1], a, b)) hed++;
            dis[a][b] = calc(con[hed], a, b);
        }
    }
}

struct Point {
    int x, y;
} que[M];
int tx, ty, px, py;
const int fx[] = {1, 0, -1, 0};
const int fy[] = {0, 1, 0, -1};
bool vis[N][N];
bool bfs(int md) {
    rep(i, 1, n) rep(j, 1, m) vis[i][j] = true;
    vis[tx][ty] = false;
    if(dis[tx][ty] < md) return false;
    int hed = 1, tai = 0;
    que[++tai] = (Point) {tx, ty};
    while(hed <= tai) {
        Point o = que[hed++];
        rep(d, 0, 3) {
            Point tp = o;
            tp.x += fx[d]; tp.y += fy[d];
            if(!vis[tp.x][tp.y]) continue;
            if(dis[tp.x][tp.y] < md) continue;
            que[++tai] = tp;
            vis[tp.x][tp.y] = false;
        }
    }
    return !vis[px][py];
}

int main() {
    // freopen("data.in", "r", stdin);
    scanf("%d%d", &n, &m);
    scanf("%d%d%d%d", &tx, &ty, &px, &py);
    rep(i, 1, m) {
        vec[i][++vec[i][0]] = -2000;
        vec[i][++vec[i][0]] = 3000;
    }
    scanf("%d", &p);
    rep(i, 1, p) {
        int x, y;
        scanf("%d%d", &x, &y);
        vec[y][++vec[y][0]] = x;
    }
    rep(i, 1, m) sort(vec[i] + 1, vec[i] + 1 + vec[i][0]);
    getDis();
    int L = 1, R = 2e6, ans = 0, md;
    while(L <= R) {
        md = L + R >> 1;
        if(bfs(md)) ans = md, L = md + 1;
        else R = md - 1;
    }
    printf("%d\n", ans);
    /*
    rep(i, 1, n) {
        rep(j, 1, m) 
            printf("%4d ", dis[i][j]);
        puts("");
    }
    */
    return 0;
}