#P3199. [Sdoi2013]escape

    ID: 2375 传统题 1000ms 512MiB 尝试: 414 已通过: 135 难度: 8 上传者: 标签>难度分类提高+/省选-计算几何Voronoi 图半平面交直线相交枚举与搜索广度优先搜索CF2400

[Sdoi2013]escape

[SDOI2013] 逃考

题目描述

高考临近,小杨的亲戚们来到他家,督促他复习。小杨想避开他们,从家里溜出去。

小杨的家是一个矩形,左下角为 (0,0)(0,0),右上角为 (x1,y1)(x_1,y_1)。nn 位亲戚驻守在不同的位置。矩形内的每个位置由距离它最近的亲戚监控。若有多位亲戚并列最近,他们都在监控该位置。距离指平面上的欧氏距离。例如,点 (3,3)(3,3) 到 (3,0)(3,0) 和 (6,7)(6,7) 的距离分别是 33 和 55,这两个亲戚中只有前者监控该点。

小杨从 (x0,y0)(x_0,y_0) 出发,可以沿任意连续路线走到矩形边界,途中可经过任意实数坐标。若路线经过一位亲戚监控的任何位置,这位亲戚就会发现他。同一个人多次发现只计一次。求最少会有多少人发现他。有亲戚时,保证出发点恰好被一人监控。

输入格式

第一行包含一个正整数 tt(t≤3t\le 3),表示数据组数。

每组数据第一行包含一个整数 nn,表示亲戚数。第二行包含四个正整数 x1,y1,x0,y0x_1,y_1,x_0,y_0。接下来 nn 行,每行包含两个正整数,表示一位亲戚的位置。正式数据中亲戚的位置互不相同,并且位于矩形内部。下列原样例第二组保留一个矩形外位置作为明确的样例特例,仍按同样的欧氏距离监控规则计算。

输出格式

对于每组数据输出一行一个整数,表示最少发现小杨的人数。

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

样例解释

第一组数据中,小杨可以直接向上走,只有 (5,6)(5,6) 处的亲戚发现他。

第二组数据中,小杨先经过 (9,9)(9,9),然后向上走到边界,会被 (7,7)(7,7) 和 (7,11)(7,11) 处的两位亲戚发现。归档样例保留了坐标 (2,20)(2,20),它位于该组的矩形之外。

数据范围

前 50%50\% 的数据满足 n≤200n\le 200,其余数据满足 n≤600n\le 600。若 n=0n=0,答案为 00。