Description：

给出一个矩形和中间的一些点，每个点监控距离这个点最近的那部分，给出初始坐标，移动这个坐标使得路线上经过的被监控的总次数最少。

$1\leqslant n\leqslant600$

Solution：

监控范围就是 $voronoi$ 图，那么我们就先把 $voronoi$ 图建出来，建图有 $O(n\log n)$ 的三角剖分转对偶图的做法，但是这里用不到，我们只要暴力枚举两两点然后把所有中线拿出来做半平面交即可，最后把在 $V$ 图上相邻的点连起来，边权为 $1$ ，在边界上的点像汇点连 $0$ 边，跑最短路就行了。

Code：

#include<algorithm>

#include<iostream>

#include<cstdlib>

#include<cstdio>

#include<cmath>

#include<queue>

#include<cctype>

#include<cstring>

using namespace std;

inline int rd()

{

	register int res = 0,f = 1;register char c = getchar();

	while(!isdigit(c)){if(c == '-')f = -1;c = getchar();}

	while(isdigit(c))res = (res << 1) + (res << 3) + c - '0',c = getchar();

	return res * f;

}

int n;

#define MAXN 610

#define db double

db X,Y,sx,sy;

struct point

{

	db x,y;

	point(double x_ = 0.0,double y_ = 0.0){x = x_;y = y_;}

}p[MAXN];

point operator + (point a,point b){return (point){a.x + b.x,a.y + b.y};}

point operator - (point a,point b){return (point){a.x - b.x,a.y - b.y};}

db operator * (point a,point b){return a.x * b.y - a.y * b.x;}

point operator * (point a,db b){return (point){a.x * b,a.y * b};}

point operator / (point a,db b){return (point){a.x / b,a.y / b};}

struct plane

{

	point p,v;

	int id;

}pl[MAXN],q[MAXN];

int head,tail;

const double eps = 1e-9;

bool equal(double a,double b){return fabs(a - b) <= eps;}

int sign(double f){return equal(f,0) ? 0 : (f > 0 ? 1 : -1);}

bool in(point p,plane k){return sign((p - k.p) * k.v) > 0;}

point intersection(plane a,plane b){return b.p + b.v * (a.v * (a.p - b.p)) / (a.v * b.v);}

double angle(point p){return atan2(p.y,p.x);}

bool cmp(plane a,plane b){return angle(a.v) < angle(b.v);}

point midpoint(point a,point b){return (point){(a.x + b.x) / 2,(a.y + b.y) / 2};}

int pltot;

point clockwise90(point k){return (point){k.y,-k.x};}

struct edge

{

	int to,nxt;

}e[MAXN * MAXN];

int edgenum = 0;

int lin[MAXN] = {0};

void add(int a,int b)

{

	e[++edgenum] = (edge){b,lin[a]};lin[a] = edgenum;

	return;

}

void build(int k)

{

	pltot = 0;

	pl[++pltot] = (plane){point(0,0),point(0,1),n + 1};

	pl[++pltot] = (plane){point(0,0),point(-1,0),n + 1};

	pl[++pltot] = (plane){point(X,Y),point(0,-1),n + 1};

	pl[++pltot] = (plane){point(X,Y),point(1,0),n + 1};

	for(int i = 1;i <= n;++i)

	{

		if(i == k)continue;

		pl[++pltot] = (plane){midpoint(p[k],p[i]),clockwise90(p[i] - p[k]),i};

	}

	sort(pl + 1,pl + 1 + pltot,cmp);

	int tot_ = 0;

	for(int i = 1;i <= pltot;++i)

	{

		if(i == 1 || !equal(angle(pl[i].v),angle(pl[tot_].v)))pl[++tot_] = pl[i];

		else if(!in(pl[tot_].p,pl[i]))pl[tot_] = pl[i];

		else continue;

	}

	pltot = tot_;

	head = 1;tail = 2;

	q[1] = pl[1];q[2] = pl[2];

	for(int i = 3;i <= pltot;++i)

	{

		while(head < tail && !in(intersection(q[tail],q[tail - 1]),pl[i]))--tail;

		while(head < tail && !in(intersection(q[head],q[head + 1]),pl[i]))++head;

		q[++tail] = pl[i];

	}

	while(head <= tail && !in(intersection(q[tail],q[tail - 1]),q[head]))--tail;

	for(int i = head;i <= tail;++i)add(k,q[i].id);

	return;

}

double dis(point a,point b){return (a.x - b.x) * (a.x - b.x) + (a.y - b.y) * (a.y - b.y);}

int loc(int x,int y)

{

	int cur;

	double d = 0x3f3f3f3f;

	for(int i = 1;i <= n;++i)

	{

		if(dis((point){x,y},p[i]) < d)

		{

			d = dis((point){x,y},p[i]);

			cur = i;

		}

	}

	return cur;

}

int d[MAXN];

bool vis[MAXN];

int dijkstra(int s)

{

	memset(vis,false,sizeof(vis));

	memset(d,0x3f,sizeof(d));

	d[s] = 0;

	priority_queue< pair<int,int> > q;

	q.push(make_pair(0,s));

	while(!q.empty())

	{

		int k = q.top().second;q.pop();

		if(vis[k])continue;

		vis[k] = true;

		for(int i = lin[k];i != 0;i = e[i].nxt)

		{

			if(d[e[i].to] > d[k] + 1)

			{

				d[e[i].to] = d[k] + 1;

				q.push(make_pair(-d[e[i].to],e[i].to));

			}

		}

	}

	return d[n + 1];

}

void work()

{

	memset(lin,0,sizeof(lin));

	edgenum = 0;

	scanf("%d",&n);

	scanf("%lf%lf%lf%lf",&X,&Y,&sx,&sy);

	for(int i = 1;i <= n;++i)scanf("%lf%lf",&p[i].x,&p[i].y);

	if(n == 0)

	{

		puts("0");

		return;

	}

	for(int i = 1;i <= n;++i)build(i);

	cout << dijkstra(loc(sx,sy)) << endl;

	return;

}

int main()

{

	int testcases = rd();

	while(testcases--)work();

	return 0;

}