Leetcode

Count Lattice Points Inside a Circle

May 26, 2022 by aAshish

  • Time:O(200^2n) = O(n)
  • Space:O(1)

C++

 
class Solution {
 public:
  int countLatticePoints(vector<vector<int>>& circles) {
    int ans = 0;

    for (int x = 0; x < 201; ++x)
      for (int y = 0; y < 201; ++y)
        ans += any_of(begin(circles), end(circles), [&](const auto& c) {
          return (c[0] - x) * (c[0] - x) + (c[1] - y) * (c[1] - y) <=
                 c[2] * c[2];
        });

    return ans;
  }
};

JAVA

 
class Solution {
  public int countLatticePoints(int[][] circles) {
    int ans = 0;

    for (int x = 0; x < 201; ++x)
      for (int y = 0; y < 201; ++y)
        for (int[] c : circles)
          if ((c[0] - x) * (c[0] - x) + (c[1] - y) * (c[1] - y) <= c[2] * c[2]) {
            ++ans;
            break;
          }

    return ans;
  }
}

Python

 
class Solution:
  def countLatticePoints(self, circles: List[List[int]]) -> int:
    return sum(any((xc - x)**2 + (yc - y)**2 <= r**2 for xc, yc, r in circles)
               for x in range(201)
               for y in range(201))