You are given a list of points on a 2D plane, represented as points, where each point is an array [x, y]. There is also your location on the plane, given as location = [x0, y0], and an angle in degrees.
You can rotate your viewing direction freely (think of standing at your location and turning your head), but your field of view is a sector of size angle degrees. A point is visible if the angle between your viewing direction and the point is less than or equal to angle/2 on either side.
The goal is to return the maximum number of points you can see at once by rotating your viewing direction appropriately. Points at your location are always visible, regardless of the direction or angle.
At first glance, you might think about checking every possible viewing direction and counting how many points are visible within the given angle. However, with up to 105 points, this brute-force approach would be far too slow.
Instead, let's reframe the problem: for each point (except those at your location), compute its angle relative to your location. Then, the problem becomes: "What is the largest number of angles that fit within any window of size angle degrees on the circle?"
This is similar to finding the longest subarray (window) with a difference between the first and last element ≤ angle, but with a circular domain (angles wrap from 359° back to 0°).
We can use a sliding window technique after sorting the angles, and handle the circularity by duplicating the angle list with each angle increased by 360°.
location. These are always visible, so we can treat them separately.atan2(y, x).angle.This approach is efficient because sorting takes O(n log n), and the sliding window is O(n).
Example Input:
points = [[2,1],[2,2],[3,3]],
angle = 90,
location = [1,1]
same_location = 0.
Result: You can see all 3 points within a 90° field of view at the right direction.
import math
class Solution:
def visiblePoints(self, points, angle, location):
same_location = 0
angles = []
x0, y0 = location
for x, y in points:
if x == x0 and y == y0:
same_location += 1
else:
dx, dy = x - x0, y - y0
theta = math.degrees(math.atan2(dy, dx))
if theta < 0:
theta += 360
angles.append(theta)
angles.sort()
n = len(angles)
# Duplicate the angles to handle wrap-around
angles += [a + 360 for a in angles]
max_cnt = left = 0
for right in range(len(angles)):
while angles[right] - angles[left] > angle:
left += 1
max_cnt = max(max_cnt, right - left + 1)
return max_cnt + same_location
#include <vector>
#include <cmath>
#include <algorithm>
using namespace std;
class Solution {
public:
int visiblePoints(vector<vector<int>>& points, int angle, vector<int>& location) {
int same_location = 0;
vector<double> angles;
int x0 = location[0], y0 = location[1];
for (auto& p : points) {
int x = p[0], y = p[1];
if (x == x0 && y == y0) {
same_location++;
} else {
double theta = atan2(y - y0, x - x0) * 180.0 / M_PI;
if (theta < 0) theta += 360.0;
angles.push_back(theta);
}
}
sort(angles.begin(), angles.end());
int n = angles.size();
for (int i = 0; i < n; ++i) {
angles.push_back(angles[i] + 360.0);
}
int max_cnt = 0, left = 0;
for (int right = 0; right < angles.size(); ++right) {
while (angles[right] - angles[left] > angle) {
left++;
}
max_cnt = max(max_cnt, right - left + 1);
}
return max_cnt + same_location;
}
};
import java.util.*;
class Solution {
public int visiblePoints(List<List<Integer>> points, int angle, List<Integer> location) {
int sameLocation = 0;
List<Double> angles = new ArrayList<>();
int x0 = location.get(0), y0 = location.get(1);
for (List<Integer> p : points) {
int x = p.get(0), y = p.get(1);
if (x == x0 && y == y0) {
sameLocation++;
} else {
double theta = Math.toDegrees(Math.atan2(y - y0, x - x0));
if (theta < 0) theta += 360.0;
angles.add(theta);
}
}
Collections.sort(angles);
int n = angles.size();
List<Double> allAngles = new ArrayList<>(angles);
for (double a : angles) {
allAngles.add(a + 360.0);
}
int maxCnt = 0, left = 0;
for (int right = 0; right < allAngles.size(); right++) {
while (allAngles.get(right) - allAngles.get(left) > angle) {
left++;
}
maxCnt = Math.max(maxCnt, right - left + 1);
}
return maxCnt + sameLocation;
}
}
var visiblePoints = function(points, angle, location) {
let sameLocation = 0;
const angles = [];
const [x0, y0] = location;
for (const [x, y] of points) {
if (x === x0 && y === y0) {
sameLocation++;
} else {
let theta = Math.atan2(y - y0, x - x0) * 180 / Math.PI;
if (theta < 0) theta += 360;
angles.push(theta);
}
}
angles.sort((a, b) => a - b);
const n = angles.length;
const allAngles = angles.concat(angles.map(a => a + 360));
let maxCnt = 0, left = 0;
for (let right = 0; right < allAngles.length; right++) {
while (allAngles[right] - allAngles[left] > angle) {
left++;
}
maxCnt = Math.max(maxCnt, right - left + 1);
}
return maxCnt + sameLocation;
};
This efficiency is possible thanks to sorting and the sliding window, both of which are much faster than brute-force for large inputs.
The key insight for this problem is to reduce the geometric challenge to a problem about angles and intervals. By converting points to angles and using a sliding window over the sorted (and duplicated) list, we can efficiently find the maximum number of visible points. Handling points at your location separately ensures correctness. This approach is both elegant and optimal for large datasets.