 # Leetcode 1828. Queries on Number of Points Inside a Circle Solution

## Problem Explanation

We are given a list of 2D points with their (x, y) coordinates, and a list of circles described by their center coordinates (x_j, y_j) and their radius r_j. Each circle is represented as a query. The task is to find out how many points from the given list of points lie inside each circle (query). Points that lie on the border of a circle are also considered inside the circle. We need to return the answer as an array with the count of points inside each query circle.

## Walk through an example

Let's walk through an example to better understand the problem:

``````1points = [[1,3],[3,3],[5,3],[2,2]]
2queries = [[2,3,1],[4,3,1],[1,1,2]]``````

For each query circle, we need to count how many points lie inside it.

1. For the first query circle with center (2, 3) and radius 1, there are 3 points inside it: (1, 3), (2, 2), (3, 3)
2. For the second query circle with center (4, 3) and radius 1, there are 2 points inside it: (3, 3), (5, 3)
3. For the third query circle with center (1, 1) and radius 2, there are 2 points inside it: (1, 3), (2, 2)

So, the final answer would be [3, 2, 2].

## Solution Approach

The basic approach to this problem is to loop through all the points of each circle in the queries list and check if the point lies inside the circle or not.

In order to check whether a point (x_i, y_i) lies inside a circle with center (x_j, y_j) and radius r_j, we can calculate the Euclidean distance between the point and the circle's center and check if it is less than or equal to the radius. The Euclidean distance can be calculated using the following formula:

``1euclidean_distance = sqrt((x_i - x_j)^2 + (y_i - y_j)^2)``

However, since we are only interested in the square of the distance, we can avoid using the square root operation, which makes the comparison faster:

``1squared_distance = (x_i - x_j)^2 + (y_i - y_j)^2``

We can now compare `squared_distance` with `r_j^2` for each point and circle center.

## Solution in Python

``````1from typing import List
2
3class Solution:
4    def countPoints(self, points: List[List[int]], queries: List[List[int]]) -> List[int]:
5        def squared_distance(x1, y1, x2, y2) -> int:
6            return (x1 - x2) ** 2 + (y1 - y2) ** 2
7
8        ans = []
9        for q in queries:
10            xj, yj, rj = q
11            count = 0
12            for p in points:
13                xi, yi = p
14                if squared_distance(xi, yi, xj, yj) <= rj ** 2:
15                    count += 1
16            ans.append(count)
17
18        return ans``````

## Solution in Java

``````1import java.util.ArrayList;
2import java.util.List;
3
4class Solution {
5    private int squaredDistance(int x1, int y1, int x2, int y2) {
6        return (x1 - x2) * (x1 - x2) + (y1 - y2) * (y1 - y2);
7    }
8
9    public List<Integer> countPoints(int[][] points, int[][] queries) {
10        List<Integer> ans = new ArrayList<>();
11        for (int[] query : queries) {
12            int xj = query, yj = query, rj = query;
13            int count = 0;
14            for (int[] point : points) {
15                int xi = point, yi = point;
16                if (squaredDistance(xi, yi, xj, yj) <= rj * rj) {
17                    count++;
18                }
19            }
21        }
22        return ans;
23    }
24}``````

## Solution in JavaScript

``````1class Solution {
2    static squaredDistance(x1, y1, x2, y2) {
3        return (x1 - x2) ** 2 + (y1 - y2) ** 2;
4    }
5
6    static countPoints(points, queries) {
7        const ans = [];
8        for (const query of queries) {
9            const xj = query, yj = query, rj = query;
10            let count = 0;
11            for (const point of points) {
12                const xi = point, yi = point;
13                if (this.squaredDistance(xi, yi, xj, yj) <= rj ** 2) {
14                    count++;
15                }
16            }
17            ans.push(count);
18        }
19        return ans;
20    }
21}``````

## Solution in C++

``````1#include <vector>
2
3class Solution {
4public:
5    int squaredDistance(int x1, int y1, int x2, int y2) {
6        return (x1 - x2) * (x1 - x2) + (y1 - y2) * (y1 - y2);
7    }
8
9    std::vector<int> countPoints(std::vector<std::vector<int>>& points, std::vector<std::vector<int>>& queries) {
10        std::vector<int> ans;
11        for (const std::vector<int>& query : queries) {
12            int xj = query, yj = query, rj = query;
13            int count = 0;
14            for (const std::vector<int>& point : points) {
15                int xi = point, yi = point;
16                if (squaredDistance(xi, yi, xj, yj) <= rj * rj) {
17                    count++;
18                }
19            }
20            ans.push_back(count);
21        }
22        return ans;
23    }
24};``````

## Solution in C#

``````1using System.Collections.Generic;
2
3public class Solution {
4    private int SquaredDistance(int x1, int y1, int x2, int y2) {
5        return (x1 - x2) * (x1 - x2) + (y1 - y2) * (y1 - y2);
6    }
7
8    public IList<int> CountPoints(int[][] points, int[][] queries) {
9        List<int> ans = new List<int>();
10        foreach (int[] query in queries) {
11            int xj = query, yj = query, rj = query;
12            int count = 0;
13            foreach (int[] point in points) {
14                int xi = point, yi = point;
15                if (SquaredDistance(xi, yi, xj, yj) <= rj * rj) {
16                    count++;
17                }
18            }