Skip to content

1610. Maximum Number of Visible Points 👎

  • Time: $O(\texttt{sort})$
  • Space: $O(n)$
 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
29
30
31
32
33
34
35
36
37
38
39
class Solution {
 public:
  int visiblePoints(vector<vector<int>>& points, int angle,
                    vector<int>& location) {
    const int posX = location[0];
    const int posY = location[1];
    int maxVisible = 0;
    int same = 0;
    vector<double> pointAngles;

    for (const vector<int>& p : points) {
      const int x = p[0];
      const int y = p[1];
      if (x == posX && y == posY)
        ++same;
      else
        pointAngles.push_back(getAngle(y - posY, x - posX));
    }

    ranges::sort(pointAngles);

    const int n = pointAngles.size();
    for (int i = 0; i < n; ++i)
      pointAngles.push_back(pointAngles[i] + 360);

    for (int l = 0, r = 0; r < pointAngles.size(); ++r) {
      while (pointAngles[r] - pointAngles[l] > angle)
        ++l;
      maxVisible = max(maxVisible, r - l + 1);
    }

    return maxVisible + same;
  }

 private:
  double getAngle(int dy, int dx) {
    return atan2(dy, dx) * 180 / M_PI;
  }
};

 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
29
30
31
32
33
34
35
36
class Solution {
  public int visiblePoints(List<List<Integer>> points, int angle, List<Integer> location) {
    final int posX = location.get(0);
    final int posY = location.get(1);
    int maxVisible = 0;
    int same = 0;
    List<Double> pointAngles = new ArrayList<>();

    for (List<Integer> p : points) {
      final int x = p.get(0);
      final int y = p.get(1);
      if (x == posX && y == posY)
        ++same;
      else
        pointAngles.add(getAngle(y - posY, x - posX));
    }

    Collections.sort(pointAngles);

    final int n = pointAngles.size();
    for (int i = 0; i < n; ++i)
      pointAngles.add(pointAngles.get(i) + 360);

    for (int l = 0, r = 0; r < pointAngles.size(); ++r) {
      while (pointAngles.get(r) - pointAngles.get(l) > angle)
        ++l;
      maxVisible = Math.max(maxVisible, r - l + 1);
    }

    return maxVisible + same;
  }

  private double getAngle(int dy, int dx) {
    return Math.atan2(dy, dx) * 180 / Math.PI;
  }
}

 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
29
30
class Solution:
  def visiblePoints(
      self,
      points: list[list[int]],
      angle: int,
      location: list[int],
  ) -> int:
    posX, posY = location
    maxVisible = 0
    same = 0
    A = []

    for x, y in points:
      if x == posX and y == posY:
        same += 1
      else:
        A.append(math.atan2(y - posY, x - posX))

    A.sort()
    A = A + [a + 2.0 * math.pi for a in A]

    angleInRadians = math.pi * (angle / 180)

    l = 0
    for r in range(len(A)):
      while A[r] - A[l] > angleInRadians:
        l += 1
      maxVisible = max(maxVisible, r - l + 1)

    return maxVisible + same