QOJ.ac

QOJ

Time Limit: 1 s Memory Limit: 128 MB Total points: 100

# 4132. 逃考

统计

高考又来了,对于不认真读书的来讲真不是个好消息。为了小杨能在家里认真读书,他的亲戚决定驻扎在他的家里监督他学习,有爷爷奶奶、外公外婆、大舅、大嫂、阿姨……

小杨实在是忍无可忍了,这种生活跟监狱有什么区别!为了他亲爱的小红,为了他的 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)$ 因为被发现的人数越少,越狱成功的机会越大,所以小杨需要你设计一条越狱路线到达矩形的边上,且被发现的人数最少。

PS:小杨做的方向是任意的,也就是说路线上的任意位置只需要是实数。

保证一开始小杨只被一个亲戚监控着。

输入格式

第一行,一个正整数 $t \leq 3$,表示数据个数。

接下来 $t$ 个数据:

  • 第一行 $n$,表示小杨的亲戚个数
  • 接下来一行四个正整数,表示矩阵右上角的坐标 $(x_1, y_1)$ 和小杨的坐标 $(x_0, y_0)$。
  • 接下来 $n$ 行,每行两个正整数,代表一个亲戚的位置。

输出格式

每个数据输出一个正整数,表示小杨越狱被发现人数的最小值。

样例数据

样例输入

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
2

子任务

  • 前 $10\%$ 的数据,$n \leq 3$;
  • 前 $50\%$ 的数据,$n \leq 200$;
  • 其余数据 $n \leq 600$。

温馨提示:根据 SDOI 传统,数据有梯度