Maximum Points in a Rotating Angle
You are given a set of $n$ points in the 2D plane and a fixed angle $\alpha$ (in radians). An "angular wedge" of width $\alpha$ is centered at the origin and can be rotated freely. Find the rotation that maximizes the number of points contained within the wedge.
**Constraints:**
-
\le n \le 10^5$
- $0 < \alpha < 2\pi$
- Points may lie anywhere in the plane (excluding the origin)
- Points on the boundary of the wedge count as contained
**Examples:**
Example 1: `points = [(1,0), (0,1), (-1,0), (0,-1)]`, `alpha = pi/2`
Output: `2` -- a quarter-circle wedge can contain at most 2 of the 4 axis-aligned points.
Example 2: `points = [(1,1), (1,2), (2,1)]`, `alpha = pi/2`
Output: `3` -- rotate the wedge to face roughly 45 degrees and all 3 points fit inside.
Open the full interactive solver, hints, and worked solution →