#11566. 统计一个圆中点的数目

内存限制:256 MiB 时间限制:1000 ms 输入文件: yds.in 输出文件: yds.out
题目类型:传统 评测方式:文本比较
上传者: Turing001

题目描述

给你一个数组 p ,其中 p[i] = [xi, yi] ,表示第 i 个点在二维平面上的坐标。多个点可能会有 相同 的坐标。

同时给你一个数组 c ,其中 c[j] = [xj, yj, rj] ,表示一个圆心在 (xj, yj) 且半径为 rj 的圆。

对于每一个查询 c[j] ,计算在第 j 个圆 内 点的数目。如果一个点在圆的 边界上 ,我们同样认为它在圆 内 。

请你输出一个数组 a ,其中 a[j] 是第 j 个查询的答案。

输入格式

第一行,n 和 m,表示 点的个数 和 圆的个数

接下来 n 行,每一行 2 个整数,表示点的 坐标 xi 和 yi

接下来 m 行,每一行 3 个整数,表示 圆心的坐标 xj 和 yj,以及半径 rj

输出格式

一行,m 个数,表示 每个圆(包括圆周)中包含的 点的个数

样例

示例 1:

输入:

4 3
1 3
3 3
5 3
2 2
2 3 1
4 3 1
1 1 2

输出:

3 2 2

解释:所有的点和圆如上图所示。
c[0] 是绿色的圆,c[1] 是红色的圆,c[2] 是蓝色的圆。

示例 2:

输入:

5 4
1 1
2 2
3 3
4 4
5 5
1 2 2
2 2 2
4 3 2
4 3 3

输出:

2 3 2 4

解释:所有的点和圆如上图所示。
c[0] 是绿色的圆,c[1] 是红色的圆,c[2] 是蓝色的圆,c[3] 是紫色的圆。

数据范围与提示

1 <= n <= 500

1 <= m <= 500

0 <= x​​​​​​i, y​​​​​​i <= 500

0 <= xj, yj <= 500

1 <= rj <= 500

所有的坐标都是整数。