Luogu

分析

其实就是要求 Voronoi 图的对偶图最短路。

可以通过半平面交求出 Voronoi 图的每个区域，然后对于每条直线连边即可。

然后直接跑 BFS 就好了。

注意特判 $n = 0$。

代码

// ===================================
//   author: M_sea
//   website: http://m-sea-blog.com/
// ===================================
#include <algorithm>
#include <iostream>
#include <cstdlib>
#include <cstring>
#include <cstdio>
#include <cmath>
#include <queue>
#define re register
using namespace std;

inline int read() {
    int X=0,w=1; char c=getchar();
    while (c<'0'||c>'9') { if (c=='-') w=-1; c=getchar(); }
    while (c>='0'&&c<='9') X=X*10+c-'0',c=getchar();
    return X*w;
}

const int N=600+10;

int n,m,r,c,sx,sy;

struct edge { int v,nxt; } e[N*N];
int head[N],e_cnt=0;

inline void addEdge(int u,int v) {
    e[++e_cnt]=(edge){v,head[u]},head[u]=e_cnt;
}

struct Point { double x,y; } a[N],p[N];
typedef Point Vector;
struct Line { Point x; Vector y; int id; double ang; } L[N];
inline int cmp(Line a,Line b) { return a.ang<b.ang; }

Point operator +(Point a,Vector b) { return (Point){a.x+b.x,a.y+b.y}; }
Vector operator -(Point a,Point b) { return (Vector){a.x-b.x,a.y-b.y}; }
Vector operator *(Vector a,double b) { return (Vector){a.x*b,a.y*b}; }
inline double cross(Vector a,Vector b) { return a.x*b.y-a.y*b.x; }
inline Vector rotate(Vector a) { return (Vector){-a.y,a.x}; }
inline Point getmid(Point a,Point b) {
    return (Point){(a.x+b.x)/2.0,(a.y+b.y)/2.0};
}
inline Point inter(Line a,Line b) {
    return a.x+a.y*(cross(b.y,b.x-a.x)/cross(b.y,a.y));
}
inline int inLeft(Point a,Line b) { return cross(b.y,a-b.x)>0; }
inline double getdis(Point a,Point b) {
    return sqrt((a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y));
}

inline void Halfplane(int s) {
    for (re int i=1;i<=m;++i) L[i].ang=atan2(L[i].y.y,L[i].y.x);
    sort(L+1,L+m+1,cmp); int h,t=1;
    for (re int i=2;i<=m;++i) {
        if (L[i].ang!=L[t].ang) L[++t]=L[i];
        else if (inLeft(L[i].x,L[t])) L[t]=L[i];
    }
    m=t,h=t=1;
    for (re int i=2;i<=m;++i) {
        while (h<t&&!inLeft(p[t],L[i])) --t;
        while (h<t&&!inLeft(p[h+1],L[i])) ++h;
        L[++t]=L[i];
        if (h<t) p[t]=inter(L[t-1],L[t]);
    }
    while (h<t&&!inLeft(p[t],L[h])) --t;
    p[h]=p[t+1]=inter(L[h],L[t]);
    for (re int i=h;i<=t;++i) addEdge(s,L[i].id);
}


int dis[N];
inline int bfs(int s) {
    memset(dis,0x3f,sizeof(dis)); dis[s]=0;
    queue<int> Q; Q.push(s);
    while (!Q.empty()) {
        int u=Q.front(); Q.pop();
        for (re int i=head[u];i;i=e[i].nxt) {
            int v=e[i].v;
            if (dis[u]+1<dis[v]) {
                dis[v]=dis[u]+1,Q.push(v);
                if (!v) return dis[v];
            }
        }
    }
}

int main() {
    int T=read();
    while (T--) {
        memset(head,0,sizeof(head)),e_cnt=0;
        n=read(),r=read(),c=read(),sx=read(),sy=read();
        for (re int i=1;i<=n;++i) a[i].x=read(),a[i].y=read();
        if (!n) { puts("0"); continue; }
        int s; double mn=2e9;
        for (re int i=1;i<=n;++i) {
            double now=getdis(a[i],(Point){sx,sy});
            if (now<mn) s=i,mn=now;
        }
        for (re int i=1;i<=n;++i) {
            m=0;
            for (re int j=1;j<=n;++j) {
                if (i==j) continue;
                L[++m]=(Line){getmid(a[i],a[j]),rotate(a[j]-a[i]),j,0};
            }
            L[++m]=(Line){(Point){0,0},(Vector){1,0},0,0};
            L[++m]=(Line){(Point){r,0},(Vector){0,1},0,0};
            L[++m]=(Line){(Point){r,c},(Vector){-1,0},0,0};
            L[++m]=(Line){(Point){0,c},(Vector){0,-1},0,0};
            Halfplane(i);
        }
        printf("%d\n",bfs(s));
    }
    return 0;
}