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
20
21
22
23
24
25
26
27
28
class Solution {
 public:
  vector<int> countPoints(vector<vector<int>>& points,
                          vector<vector<int>>& queries) {
    vector<int> ans;

    for (const vector<int>& query : queries) {
      const int xj = query[0];
      const int yj = query[1];
      const int rj = query[2];
      int count = 0;
      for (const vector<int>& point : points) {
        const int xi = point[0];
        const int yi = point[1];
        if (squared(xi - xj) + squared(yi - yj) <= squared(rj))
          ++count;
      }
      ans.push_back(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
16
17
18
19
20
21
22
23
24
25
class Solution {
  public int[] countPoints(int[][] points, int[][] queries) {
    int[] ans = new int[queries.length];

    for (int i = 0; i < queries.length; ++i) {
      final int xj = queries[i][0];
      final int yj = queries[i][1];
      final int rj = queries[i][2];
      int count = 0;
      for (int[] point : points) {
        final int xi = point[0];
        final int yi = point[1];
        if (squared(xi - xj) + squared(yi - yj) <= squared(rj))
          ++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
class Solution:
  def countPoints(self, points: List[List[int]], queries: List[List[int]]) -> List[int]:
    ans = []

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

    return ans