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 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
     
      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
      
       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)
       
        tail;                {
                    for i:=1 to en do                begin                        for j:=1 to en do                        begin                                if f[i,j]