Skip to content

1828. Queries on Number of Points Inside a Circle 👍

  • Time: $O(q|\texttt{points}|)$
  • Space: $O(q)$
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
class Solution {
 public:
  vector<int> countPoints(vector<vector<int>>& points,
                          vector<vector<int>>& queries) {
    vector<int> ans;

    auto squared = [](int x) { return x * x; };

    for (const vector<int>& q : queries) {
      const int rSquared = q[2] * q[2];
      int count = 0;
      for (const vector<int>& p : points)
        count += squared(p[0] - q[0]) + squared(p[1] - q[1]) <= rSquared;
      ans.push_back(count);
    }

    return ans;
  }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {
  public int[] countPoints(int[][] points, int[][] queries) {
    int[] ans = new int[queries.length];

    for (int i = 0; i < queries.length; ++i) {
      int[] q = queries[i];
      final int rSquared = q[2] * q[2];
      int count = 0;
      for (int[] p : points)
        if (squared(p[0] - q[0]) + squared(p[1] - q[1]) <= rSquared)
          ++count;
      ans[i] = count;
    }

    return ans;
  }

  private int squared(int x) {
    return x * x;
  }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
class Solution:
  def countPoints(self, points: List[List[int]], queries: List[List[int]]) -> List[int]:
    ans = []

    def squared(x):
      return x * x

    for xj, yj, r in queries:
      rSquared = r**2
      count = 0
      for xi, yi in points:
        count += (xi - xj)**2 + (yi - yj)**2 <= rSquared
      ans.append(count)

    return ans