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

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

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

Return an array answer, where answer[j] is the answer to the jth query.

&nbsp;
Example 1:

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.


Example 2:

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.


&nbsp;
Constraints:


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


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

class Solution:
	def countPoints(self, points: List[List[int]], queries: List[List[int]]) -> List[int]:
		circle = []
		for x2, y2, radius in queries:
			count = 0
			for x1, y1 in points:
				dis = ((x2-x1)**2+(y2-y1)**2)**0.5 # Use the Distance Formula...
				if dis <= radius:
					count += 1
			circle.append(count)
		return circle
class Solution {
    public int[] countPoints(int[][] points, int[][] queries) {
        int len = queries.length;
        int[] ans = new int[len];

        for(int i=0;i<len;i++){
            int count = 0;
            int radius2 = queries[i][2] * queries[i][2];
            for(int p=0; p<points.length;p++){
                int[] point = points[p];
                if(radius2(point,queries[i]) <= radius2){
                    count += 1;
                }
            }
            ans[i] = count;
        }

        return ans;
    }

    private int radius2(int[] point, int[] center){
        int x = point[0] - center[0];
        int y = point[1] - center[1];
        return x*x + y*y;
    }
}
class Solution {
    void buildTree(vector<vector<int>>& p, int depth, int i, int j) {
        if (j - i <= 1) return;
        
        int k = 1 - depth & 1, m = i + (j - i) / 2;
        nth_element(p.begin() + i, p.begin() + m, p.begin() + j,
                    [k](auto &a, auto& b) { return a[k] < b[k]; });
        partition(p.begin() + i, p.begin() + j,
                  [k, m, &p](auto &a){ return a[k] < p[m][k]; });

        buildTree(p, depth+1, i, m);
        buildTree(p, depth+1, m+1, j);
    }
    
    inline bool isPointInside(const vector<int> &p, const vector<int> &c) {
        return (p[0] - c[0]) * (p[0] - c[0]) + (p[1] - c[1]) * (p[1] - c[1]) <= c[2] * c[2];
    }

    int pointsInside(const vector<vector<int>> &t, const vector<int> &q, int depth,
                    int i, int j) {
        if (j == i) return 0;
        else if (j - i == 1) return isPointInside(t[i], q);
        
        int k = 1 - depth & 1, m = i + (j - i) / 2, diff = t[m][k] -  q[k];
        if (diff > q[2]) return pointsInside(t, q, depth+1, i, m);
        else if (diff < -q[2]) return pointsInside(t, q, depth+1, m+1, j);
        else
            return pointsInside(t, q, depth+1, i, m)
                + isPointInside(t[m], q)
                + pointsInside(t, q, depth+1, m+1, j);
    }
public:
    vector<int> countPoints(vector<vector<int>>& points, vector<vector<int>>& queries) {
        buildTree(points, 0, 0, points.size());

        vector<int> res(queries.size());
        for (size_t i = 0; i < queries.size(); ++i)
            res[i] = pointsInside(points, queries[i], 0, 0, points.size());
        return res;
    }
};
var countPoints = function(points, queries) {
    const getDistance = (x1,y1,x2,y2) => {
        return Math.sqrt((x1-x2) * (x1-x2) + (y1-y2) * (y1-y2));
    }
    
    let output = [];
    
    queries.forEach(([a,b,r]) => {
        let count = 0;
        points.forEach(([x,y]) => {
            if(getDistance(a,b,x,y) <= r) count += 1;
        });
        output.push(count);
    });
 
    return output;
};
Queries on Number of Points Inside a Circle