#P3199. [Sdoi2013]escape
[Sdoi2013]escape
[SDOI2013] 逃考
题目描述
高考临近,小杨的亲戚们来到他家,督促他复习。小杨想避开他们,从家里溜出去。
小杨的家是一个矩形,左下角为 ,右上角为 。 位亲戚驻守在不同的位置。矩形内的每个位置由距离它最近的亲戚监控。若有多位亲戚并列最近,他们都在监控该位置。距离指平面上的欧氏距离。例如,点 到 和 的距离分别是 和 ,这两个亲戚中只有前者监控该点。
小杨从 出发,可以沿任意连续路线走到矩形边界,途中可经过任意实数坐标。若路线经过一位亲戚监控的任何位置,这位亲戚就会发现他。同一个人多次发现只计一次。求最少会有多少人发现他。有亲戚时,保证出发点恰好被一人监控。
输入格式
第一行包含一个正整数 (),表示数据组数。
每组数据第一行包含一个整数 ,表示亲戚数。第二行包含四个正整数 。接下来 行,每行包含两个正整数,表示一位亲戚的位置。正式数据中亲戚的位置互不相同,并且位于矩形内部。下列原样例第二组保留一个矩形外位置作为明确的样例特例,仍按同样的欧氏距离监控规则计算。
输出格式
对于每组数据输出一行一个整数,表示最少发现小杨的人数。
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
样例解释
第一组数据中,小杨可以直接向上走,只有 处的亲戚发现他。
第二组数据中,小杨先经过 ,然后向上走到边界,会被 和 处的两位亲戚发现。归档样例保留了坐标 ,它位于该组的矩形之外。
数据范围
前 的数据满足 ,其余数据满足 。若 ,答案为 。