Description
高考又来了，对于不认真读书的来讲真不是个好消息。为了小杨能在家里认真读书，他的亲戚决定驻扎在他的家里监督他学习，有爷爷奶奶、外公外婆、大舅、大嫂、阿姨……
小杨实在是忍无可忍了，这种生活跟监狱有什么区别！为了他亲爱的小红，为了他的dota，他决定越狱！
假设小杨的家是个n*m 的矩阵，左下角坐标为（0，0），右上角坐标为（x1，y1）。小杨有n 个亲戚，驻扎在矩阵里（位置不同，且不在矩阵的边上）。小杨家里的每个地方都被亲戚监控着，而且只被距离最近的亲戚监控：
也就是说假设小杨所在的位置是（3,3），亲戚A 在（3,0），A 距离小杨距离是3；亲戚B 在（6,7），则B 距离小杨距离是5。距离A < 距离B，所以（3,3）位置由A 监控。
如果“最近距离”出现同时有几个亲戚，那么那个位置同时被那几个亲戚监控。
给出小杨的坐标（x0,y0）。因为被发现的人数越少，越狱成功的机会越大，所以小杨需要你设计一条越狱路线到达矩形的边上，且被发现的人数最少。
Ps：小杨做的方向是任意的，也就是说路线上的任意位置只需要是实数。
保证一开始小杨只被一个亲戚监控着。
Input
第一行，一个正整数t<=3，表示数据个数。
接下来t 个数据：
第一行n，表示小杨的亲戚个数。
接下来一行四个正整数，表示矩形右上角的坐标（x1,y1）和小杨的坐标（x0,y0）。
接下来n 行，每行两个正整数，代表一个亲戚的位置。
Output
每个数据输出一个正整数，表示小杨越狱被发现人数的最小值。
Sample Input
3
4
10 10 5 5
5 6
3 5
7 5
5 3
0
10 10 5 5
3
3 3 2 2
1 1
2 2
2 1
Sample Output
1
0
1
Data Constraint
前50%数据，n<=200；
其余数据n<=600。
Hint
样例解释：
第一个数据，小杨直接往上走，只被（5,6）监控过。
第二个数据，小杨被（7,7）监控，走到（9,9）被（7,11）监控，然后直接往上走。
题解
此题再次证实——比赛千万别死磕计算几何
虽然我也只是磕了2个小时
题意应该很好懂。
一个显然的性质：
为了便于逃跑，小杨尽量往亲戚点跑，经过的亲戚可能性越小~~（最危险的地方最安全）~~
我们有一个很容易想到的方法：
考虑建图，把任意两个亲戚间互相到达的最小代价求出来，跑最短路即可。
怎么求是个问题。
我们看到一个性质——
对于两个亲戚，当且仅当小杨走到两点线段间的中垂线时，才是被两个亲戚同时监控。
一个直观的想法——这个中垂线是否可以当分界线呢？
由于一个中垂线把平面分成两半，于是我们可以考虑到对于一个i，把i与其他亲戚的所有中垂线求出来。
然后，可以发现，这些中垂线可以围成一个区域，而这个区域则是当且亲戚i所控制的区域。
这不是显然半平面交吗？
直接暴力搞。时间不多。
搞出来有什么用呢？
我们又发现，如果小杨从i通过半平面交上一条i与j之间的中垂线到达j，代价是花费1的。
不就可以建图连边了吗？
完美解决。
问题来了，这么找到结束的点的位置？
直接把矩形的四条边丢进半平面交即可。
当然，细节极多，调了我近3h。
标程
代码不多，也就9k
不多不多，多乎哉，不多也。
type
nod=record
x,y:real;
end;
point=record
x,y:real;
end;
line=record
a,b:nod;
end;
new=record
x,y,jj,jl:extended;
kind,bh:longint;
end;
var
i,j,k,l,n,m,q,zx,zd,ex,ey,sx,sy,ans,st,en,gs,head,tail,took:longint;
spot:array[1..600] of new;
f:array[1..600,1..600] of longint;
x,y:array[1..600] of longint;
a:array[1..100000] of longint;
map,id,dl:array[0..600] of longint;
bz:array[1..600] of boolean;
op:array[0..600] of line;
mid:extended;
function vectorjia(a,b:nod):nod;
var
c:nod;
begin
c.x:=a.x+b.x;c.y:=a.y+b.y;
exit(c);
end;
function vectorjian(a,b:nod):nod;
var
c:nod;
begin
c.x:=a.x-b.x;c.y:=a.y-b.y;
exit(c);
end;
function vectorcheng(a:nod;b:real):nod;
var
c:nod;
begin
c.x:=a.x*b;c.y:=a.y*b;
exit(c);
end;
function cross(a,b:nod):real;
begin
exit(a.x*b.y-a.y*b.x);
end;
function dist(a,b:point):real;
begin
exit(sqrt((a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y)));
end;
function dotji(a,b:nod):real;
begin
exit(a.x*b.x+a.y*b.y);
end;
procedure qsort(l,r:longint);
var
i,j:longint;
m,m1:extended;
k:new;
o:extended;
begin
i:=l;j:=r;
m:=spot[(l+r) div 2].jj;
m1:=spot[(l+r) div 2].jl;
repeat
while (spot[i].jj>m) or ((spot[i].jj=m) and (spot[i].jl<m1)) do inc(i);
while (spot[j].jj<m) or ((spot[j].jj=m) and (spot[j].jl>m1)) do dec(j);
if i<=j then
begin
k:=spot[i];spot[i]:=spot[j];spot[j]:=k;
op[0]:=op[i];op[i]:=op[j];op[j]:=op[0];
id[0]:=id[i];id[i]:=id[j];id[j]:=id[0];
inc(i);dec(j);
end;
until i>j;
if l<j then qsort(l,j);
if r>i then qsort(i,r);
end;
procedure hpi(n:longint);
var
i,j,k,first,last:longint;
miny,minx:extended;
xian,q:array[0..50000] of line;
p:array[0..50000] of point;
jj:array[0..50000] of real;
bz:array[1..10000] of boolean;
ee:array[1..10000] of longint;
pp:point;
kk:nod;
function onleft(l:line;p:point):boolean;
var
a:nod;
begin
a.x:=p.x-l.a.x;a.y:=p.y-l.a.y;
if cross(l.b,a)>0 then exit(true) else
exit(false);
end;
function getpoint(a,b:line):point;
var
c,aa:nod;
t,p1,p2:real;
begin
c:=vectorjian(a.a,b.a);
p1:=cross(b.b,c);
p2:=cross(a.b,b.b);
t:=p1/p2;
aa:=vectorjia(a.a,vectorcheng(a.b,t));
getpoint.x:=aa.x;
getpoint.y:=aa.y;
end;
begin
for i:=1 to n do
begin
if (op[i].b.y=0) and (op[i].b.x>0) then spot[i].jj:=0 else
if (op[i].b.y=0) and (op[i].b.x<0) then spot[i].jj:=180 else
if (op[i].b.x=0) and (op[i].b.y>0) then spot[i].jj:=90 else
if (op[i].b.x=0) and (op[i].b.y<0) then spot[i].jj:=270 else
if op[i].b.y>0 then
begin
if op[i].b.x<0 then spot[i].jj:=arctan(op[i].b.y/op[i].b.x)*(180/pi)+180
else if op[i].b.x>0 then spot[i].jj:=arctan(op[i].b.y/op[i].b.x)*(180/pi);
end
else
if op[i].b.y<0 then
begin
if op[i].b.x<0 then spot[i].jj:=arctan(op[i].b.y/op[i].b.x)*(180/pi)+180
else if op[i].b.x>0 then spot[i].jj:=arctan(op[i].b.y/op[i].b.x)*(180/pi)+360;
end;
kk.x:=x[st]-spot[i].x;kk.y:=y[st]-spot[i].y;
spot[i].jl:=abs(cross(op[i].b,kk))/sqrt(sqr(op[i].a.x-op[i].b.x)+sqr(op[i].a.y-op[i].b.y));
end;
qsort(1,n);
for i:=1 to n do
begin
xian[i]:=op[i];
end;
fillchar(bz,sizeof(bz),true);
for i:=2 to n do
begin
if spot[i].jj=spot[i-1].jj then
begin
bz[i]:=false;
end;
end;
first:=1;last:=1;
fillchar(q,sizeof(q),0);
fillchar(p,sizeof(p),0);
q[1]:=xian[1];
ee[1]:=id[1];
for i:=2 to n do
begin
if not bz[i] then continue;
while (first<last) and (onleft(xian[i],p[last-1])) do dec(last);
while (first<last) and (onleft(xian[i],p[first])) do inc(first);
inc(last);
ee[last]:=id[i];
q[last]:=xian[i];
if cross(q[last].b,q[last-1].b)=0 then
begin
dec(last);
pp.x:=xian[i].a.x;pp.y:=xian[i].a.y;
if onleft(q[last],pp) then
begin
q[last]:=xian[i];
end;
end;
if first<last then
begin
p[last-1]:=getpoint(q[last-1],q[last]);
end;
end;
while (first<last) and (onleft(q[first],p[last-1])) do dec(last);
for i:=first to last do
begin
if ee[i]=en then f[st,en]:=0
else
f[st,ee[i]]:=1;
end;
end;
procedure bfs(dep:longint);
var
i,j,k,l:longint;
begin
for i:=1 to en do
begin
//if not bz[i] then
begin
if map[i]>map[a[dep]]+f[a[dep],i] then
begin
inc(took);
a[took]:=i;
bz[i]:=true;
map[i]:=map[a[dep]]+f[a[dep],i];
end;
end;
end;
end;
begin
//assign(input,'0data.in');reset(input);
readln(q);
while q>0 do
begin
q:=q-1;
readln(n);
readln(ex,ey,sx,sy);
for i:=1 to n do
begin
readln(x[i],y[i]);
spot[i].x:=x[i];
spot[i].y:=y[i];
end;
if n=0 then
begin
writeln(0);
continue;
end;
fillchar(f,sizeof(f),127 div 3);
zd:=f[1,1];
en:=n+1;
zx:=1;
for i:=1 to n do
begin
k:=0;
for j:=1 to n do
begin
if i<>j then
begin
inc(k);
spot[k].x:=x[j];
spot[k].y:=y[j];
op[k].b.x:=(y[j]-y[i])*10000;
op[k].b.y:=-(x[j]-x[i])*10000;
op[k].a.x:=(x[i]+x[j])/2-op[k].b.x;
op[k].a.y:=(y[i]+y[j])/2-op[k].b.y;
id[k]:=j;
end;
end;
inc(k);spot[k].x:=0;spot[k].y:=0;op[k].b.x:=0;op[k].b.y:=ey;op[k].a.x:=0;op[k].a.y:=0;id[k]:=en;
inc(k);spot[k].x:=0;spot[k].y:=ey;op[k].b.x:=ex;op[k].b.y:=0;op[k].a.x:=0;op[k].a.y:=ey;id[k]:=en;
inc(k);spot[k].x:=ex;spot[k].y:=ey;op[k].b.x:=0;op[k].b.y:=-ey;op[k].a.x:=ex;op[k].a.y:=ey;id[k]:=en;
inc(k);spot[k].x:=ex;spot[k].y:=0;op[k].b.x:=-ex;op[k].b.y:=0;op[k].a.x:=ex;op[k].a.y:=0;id[k]:=en;
st:=i;
hpi(k);
end;
for i:=2 to n do
begin
if sqr(x[i]-sx)+sqr(y[i]-sy)<sqr(x[zx]-sx)+sqr(y[zx]-sy) then
zx:=i;
end;
head:=1;tail:=1;took:=1;
a[1]:=zx;
fillchar(bz,sizeof(bz),false);
fillchar(map,sizeof(map),127 div 3);
map[zx]:=1;
bz[zx]:=true;
repeat
for i:=head to tail do
bfs(i);
head:=tail+1;
tail:=took;
until head>tail;
{
for i:=1 to en do
begin
for j:=1 to en do
begin
if f[i,j]<zd then
begin
write(f[i,j],' ');
end
else
write(0,' ');
end;
writeln;
end;
}
writeln(map[en]);
end;
end.
end.