You are standing at the origin on a 2D plane. You are given a list of points points[i] = (xi, yi) (not necessarily distinct), and a viewing angle theta in degrees.
You may choose any viewing direction (a ray starting from the origin). Your field of view is the closed sector of angular width theta whose central axis is your chosen direction (equivalently, a window of size theta when sweeping directions around the origin).
A point is considered visible if the angle from the positive x-axis to the vector (xi, yi) lies within that angular sector (after choosing the sector’s placement). Points exactly on the boundary are visible. If any points are exactly at the origin (0,0), they are always visible regardless of direction.
Task: Choose a viewing direction that maximizes the number of visible points.
Output:
-
Return the maximum number of visible points, and
-
Return any one viewing direction (e.g., an angle in degrees in
[0, 360)
) that achieves this maximum.
Constraints (typical interview scale):
-
1 <= n <= 2e5
-
xi, yi
are integers (e.g., in
[-1e9, 1e9]
)
-
0 < theta <= 360
Notes:
-
Angles wrap around at
360°
.
-
Your solution should be better than
O(n^2)
.