## Maximum Number of Visible Points

• Time:O(n\log n)
• Space:O(n)

## C++

``````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 auto& 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;
}
};
``````

## JAVA

``````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)

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;
}
}
``````

## Python

``````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
``````