C. 灯塔警戒

    传统题 1000ms 256MiB

灯塔警戒

该比赛已结束,您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

海岸线上有 nn 座灯塔,第 ii 座灯塔的位置为 (xi,yi)(x_i,y_i)。其中有 kk 座灯塔被设为重点保护灯塔。

现在有 TT 个观测点。对于每个观测点,系统会找到距离它最远的一座灯塔;如果有多座灯塔距离相同,则选择编号最小的那一座。若被找到的灯塔是重点保护灯塔,则这个观测点会触发一次警戒。 $(x_1,y_1) (x_2, y_2) 的距离 \sqrt{(x_1-x_2)^2+(y_1-y_2)^2}$

请你统计一共有多少个观测点会触发警戒。

输入格式

第一行三个整数 n,k,Tn,k,T

接下来 nn 行,每行两个整数 xi,yix_i,y_i,表示第 ii 座灯塔的位置。

接下来 kk 行,每行两个整数,表示一座重点保护灯塔的位置。保证这些位置都在前面的 nn 座灯塔中出现。

接下来 TT 行,每行两个整数,表示一个观测点的位置。

输出格式

输出一个整数,表示触发警戒的观测点数量。

样例 #1

样例输入 #1

4 2 2
-1 0
0 -1
2 0
0 2
-1 0
0 2
3 0
0 0

样例输出 #1

1

数据范围

对于所有数据,保证 1kn1\le k\le n,所有灯塔位置两两不同,重点保护灯塔的位置一定在前 nn 座灯塔中出现。

测试点占比 数据范围
30%30\% 1n501\le n\le 501T501\le T\le 50,坐标绝对值不超过 5050
60%60\% 1n3001\le n\le 3001T3001\le T\le 300,坐标绝对值不超过 300300
100%100\% 1n10001\le n\le 10001T10001\le T\le 1000,坐标绝对值不超过 10001000

【ZCX-011-DIV3】智程星周赛011(入门组)

未参加
状态
已结束
规则
乐多
题目
4
开始于
2026-6-2 21:30
结束于
2026-6-9 17:30
持续时间
2 小时
主持人
参赛人数
17