# 1610. Maximum Number of Visible Points

• Time: $O(n\log n)$
• 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>& points, int angle, vector& location) { const int posX = location[0]; const int posY = location[1]; int maxVisible = 0; int same = 0; vector pointAngles; for (const vector& 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)); } sort(begin(pointAngles), end(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> points, int angle, List location) { final int posX = location.get(0); final int posY = location.get(1); int maxVisible = 0; int same = 0; List pointAngles = new ArrayList<>(); for (List 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 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