#B1506. 最远点合法的起点数
最远点合法的起点数
【题目描述】
地图中共有 台密码机,第 台密码机的坐标为 。
有 名求生者,每名求生者选择一台密码机作为出生点,被选择的密码机称为出生密码机。接下来有 个监管者出生点。
对于每个监管者出生点,需要封禁距离该出生点最远的密码机。如果有多台密码机距离相同且都是最远的,则封禁其中编号最小的密码机。
请计算在这 个监管者出生点中,有多少个出生点会封禁一台出生密码机。
两点 和 的距离为 。
【输入描述】
输入共 行。
第一行输入三个整数 ,分别表示密码机数量、出生密码机数量和监管者 出生点数量。
接下来 行,每行输入一台密码机的坐标 。
接下来 行,每行输入一台出生密码机的坐标。保证这些坐标在前面出现过。
接下来 行,每行输入一个监管者出生点坐标。
保证:
- ;
- ;
- 坐标满足 ;
- 每个出生密码机坐标都与某台密码机的坐标完全相同。
【输出描述】
输出一行一个整数,表示会封禁出生密码机的监管者出生点数量。
【样例 1】
【样例 1 输入】
4 2 2
-1 0
0 -1
2 0
0 2
-1 0
0 2
3 0
0 0
【样例 1 输出】
1
【样例 1 解释】
第一台和第四台密码机是出生密码机。
对于监管者出生点 ,第一台密码机距离为 ,是最远密码机,因此该出生点会封禁一台出生密码机。
对于监管者出生点 ,第三台和第四台密码机距离相同且最远,根据“距离相同则选择编号最小”的规则,最终封禁第三台密码机。
只有一个监管者出生点封禁了出生密码机,因此答案为 。
【数据规模与约定】
| 测试点编号 | 分数 | 特殊性质 |
|---|---|---|
1 |
10 | |
2 |
||
3 ~ 4 |
20 | 密码机与出生点的横坐标均为 |
5 |
10 | |
6 |
||
7 ~ 10 |
40 | 无特殊性质 |