[SDOI2013] 逃考

题目描述

髙考又来了,对于不认真读书的来讲真不是个好消息为了小杨能在家里认真读书,他的亲戚决定驻扎在他的家里监督他学习,有爷爷奶奶、外公外婆、大舅、大嫂、阿姨 ......。 小杨实在是忍无可忍了,这种生活跟监狱有什么区别!为了他亲爱的小红,为了他的 dota, 他决定越狱! 假设小杨的家是个 $n\times m$ 的矩阵,左下角坐标为($0,0)$,右上角坐标为($x_1,y_1)$。小杨有 $n$ 个亲戚,驻扎在矩阵里(位置不同,且不在矩阵的边上)。小杨家里的每个地方都被亲戚监控着,而且只被距离最近的亲戚监控: 也就是说假设小杨所在的位置是($3,3)$, 亲戚 $A$ 在($3,0)$,A 距离小杨距离是 $3$;亲戚 $B$ 在($6,7),$ 则 $B$ 距离小杨距离是 $5$。距离 $A<$ 距离 $B$,所以($3,3)$ 位置由 $A$ 监控。 如果“最近距离”出现同时有几个亲戚,那么那个位置同时被那几个亲戚监控。 给出小杨的坐标($x_0,y_0)$。因为被发现的人数越少,越狱成功的机会越大,所以小杨需要你设计一条越狱路线到达矩形的边上,且被发现的人数最少。 小杨做的方向是任意的,也就是说路线上的任意位置 $H$ 需要是实数。 保证一开始小杨只被一个亲戚监控着。

输入输出格式

输入格式


第一行一个正整数 $t \le 3$ 表示数据个数。 接下来 $t$ 个数据: 第一行 $n$ 表示亲戚个数。 第二行 $4$ 个正整数表示举行右上角坐标 $(x_1,y_1)$ 和小杨的坐标 $(x_0,y_0)$。 接下来 $n$ 行,每行 $2$ 个正整数表示一个亲戚的位置。

输出格式


每个数据一个正整数表示越狱被发现人数的最小值

输入输出样例

输入样例 #1

2
4
10 10 5 5
5 6
3 5
7 5
5 3
17
14 12 7 6
7 11
6 9
7 7
1 10
2 20
1 6
2 6
1 1
2 2
5 1
5 2
13 1
12 2
12 7
13 7
12 11
13 11

输出样例 #1

1
2

说明

数据解释 :。 第一个数据,小杨直接往上走,只被 $(5,6)$ 监控过。 第二个数据,小杨被 $(7,7)$ 监控 - 走到 $(9,9)$ 被 $(7,11)$ 监控,然后直接往上走。 数据规模 : 前 $50\%$ 数据, $n \le 200$。 其余数据 $n \le 600$。