分析
其实就是要求 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;
}