queries-on-number-of-points-inside-a-circle

java

python

python3

mysql

mssql

oraclesql

csharp

javascript

typescript

bash

swift

kotlin

dart

golang

ruby

scala

rust

racket

erlang

elixir

pythondata

postgresql

cangjie

Algorithms

You are given an array <code>points</code> where <code>points[i] = [xi, yi]</code> is the coordinates of the <code>ith</code> point on a 2D plane. Multiple points can have the same coordinates.

You are also given an array <code>queries</code> where <code>queries[j] = [xj, yj, rj]</code> describes a circle centered at <code>(xj, yj)</code> with a radius of <code>rj</code>.

For each query <code>queries[j]</code>, compute the number of points inside the <code>jth</code> circle. Points on the border of the circle are considered inside.

Return an array <code>answer</code>, where <code>answer[j]</code> is the answer to the <code>jth</code> query.

&nbsp;
Example 1:
<img alt="" src="https://assets.leetcode.com/uploads/2021/03/25/chrome_2021-03-25_22-34-16.png" style="width: 500px; height: 418px;" />
<pre>
Input: points = [[1,3],[3,3],[5,3],[2,2]], queries = [[2,3,1],[4,3,1],[1,1,2]]
Output: [3,2,2]
Explanation: The points and circles are shown above.
queries[0] is the green circle, queries[1] is the red circle, and queries[2] is the blue circle.
</pre>

Example 2:
<img alt="" src="https://assets.leetcode.com/uploads/2021/03/25/chrome_2021-03-25_22-42-07.png" style="width: 500px; height: 390px;" />
<pre>
Input: points = [[1,1],[2,2],[3,3],[4,4],[5,5]], queries = [[1,2,2],[2,2,2],[4,3,2],[4,3,3]]
Output: [2,3,2,4]
Explanation: The points and circles are shown above.
queries[0] is green, queries[1] is red, queries[2] is blue, and queries[3] is purple.
</pre>

&nbsp;
Constraints:

<ul>
	<li><code>1 &lt;= points.length &lt;= 500</code></li>
	<li><code>points[i].length == 2</code></li>
	<li><code>0 &lt;= x​​​​​​i, y​​​​​​i &lt;= 500</code></li>
	<li><code>1 &lt;= queries.length &lt;= 500</code></li>
	<li><code>queries[j].length == 3</code></li>
	<li><code>0 &lt;= xj, yj &lt;= 500</code></li>
	<li><code>1 &lt;= rj &lt;= 500</code></li>
	<li>All coordinates are integers.</li>
</ul>

&nbsp;
Follow up: Could you find the answer for each query in better complexity than <code>O(n)</code>?

countPoints

Queries on Number of Points Inside a Circle

Count Lattice Points Inside a Circle

count-lattice-points-inside-a-circle

统计圆内格点数目

Count Number of Rectangles Containing Each Point

count-number-of-rectangles-containing-each-point

统计包含每个点的矩形数目

Check if the Rectangle Corner Is Reachable

check-if-the-rectangle-corner-is-reachable

判断矩形的两个角落是否可达

Geometry

Array

Math

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

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

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

请你返回一个数组 <code>answer</code> ，其中 <code>answer[j]</code>是第 <code>j</code> 个查询的答案。

 

示例 1：
<img alt="" src="https://assets.leetcode.com/uploads/2021/03/25/chrome_2021-03-25_22-34-16.png" style="width: 500px; height: 418px;">
<pre>输入：points = [[1,3],[3,3],[5,3],[2,2]], queries = [[2,3,1],[4,3,1],[1,1,2]]
输出：[3,2,2]
解释：所有的点和圆如上图所示。
queries[0] 是绿色的圆，queries[1] 是红色的圆，queries[2] 是蓝色的圆。
</pre>

示例 2：
<img alt="" src="https://assets.leetcode.com/uploads/2021/03/25/chrome_2021-03-25_22-42-07.png" style="width: 500px; height: 390px;">
<pre>输入：points = [[1,1],[2,2],[3,3],[4,4],[5,5]], queries = [[1,2,2],[2,2,2],[4,3,2],[4,3,3]]
输出：[2,3,2,4]
解释：所有的点和圆如上图所示。
queries[0] 是绿色的圆，queries[1] 是红色的圆，queries[2] 是蓝色的圆，queries[3] 是紫色的圆。
</pre>

 

提示：

<ul>
	<li><code>1 &lt;= points.length &lt;= 500</code></li>
	<li><code>points[i].length == 2</code></li>
	<li><code>0 &lt;= x​​​​​​i, y​​​​​​i &lt;= 500</code></li>
	<li><code>1 &lt;= queries.length &lt;= 500</code></li>
	<li><code>queries[j].length == 3</code></li>
	<li><code>0 &lt;= xj, yj &lt;= 500</code></li>
	<li><code>1 &lt;= rj &lt;= 500</code></li>
	<li>所有的坐标都是整数。</li>
</ul>