Maximum Points in a Rotating Angle

Worked Solution

How to Think About It: The wedge is a pie slice of fixed angular width $\alpha$; only each point's *angle* from the origin matters, never its distance. Rotating the wedge = sliding a window of angular width $\alpha$ around the circle and counting how many angles fall inside. The key extremal fact (the "push-to-the-boundary" heuristic): the optimal window can always be slid until its trailing edge sits exactly on some point. So you never need to test infinitely many rotations — only the $n$ rotations that start each window at an existing point's angle. That turns a continuous optimization into a sorted-array sliding window. The one trap is the wrap-around at $\pm\pi$: a window can straddle the seam, which a naive linear scan misses.

Quick Estimate: Check the logic on Example 2, [(1,1),(1,2),(2,1)], $\alpha = \pi/2 = 90^\circ$, by eye. Angles: $(1,1)$ is $45^\circ$; $(2,1) = \arctan(1/2) \approx 27^\circ$; $(1,2) = \arctan 2 \approx 63^\circ$. All three sit inside $[27^\circ, 63^\circ]$, a spread of only $36^\circ < 90^\circ$, so a single $90^\circ$ wedge aimed near $45^\circ$ swallows all three — answer $3$, matching. For Example 1 the four axis points are $90^\circ$ apart; a *closed* $90^\circ$ wedge catches two adjacent ones (e.g. $0^\circ$ and $90^\circ$ on its boundaries) — answer $2$. Both fall straight out of "how many angles fit in a $\alpha$-wide arc."

Approach: Polar-sort angles, duplicate with $+2\pi$, two-pointer window of width $\alpha$.

Formal Solution:

1. Map each point to $\theta_i = \text{atan2}(y,x) \in (-\pi,\pi]$.
2. Sort the $n$ angles ascending.
3. Un-wrap the circle: append $\theta_i + 2\pi$ for every angle, yielding a sorted length-$2n$ array. A window that crosses the $\pm\pi$ seam now appears as a contiguous run in this doubled array, so no modular arithmetic is needed in the loop.
4. Two-pointer sweep: for each left index $i \in [0,n)$, advance a right pointer $j$ while $\theta_j - \theta_i \le \alpha$. The count $j - i$ is how many points a wedge whose trailing edge is at $\theta_i$ contains. Track the max.

```python import math

def max_points_in_angle(points, alpha): angles = sorted(math.atan2(y, x) for x, y in points) n = len(angles) angles = angles + [a + 2 * math.pi for a in angles] # un-wrap max_count = 0 j = 0 for i in range(n): if j < i: j = i while j < 2 * n and angles[j] - angles[i] <= alpha: j += 1 max_count = max(max_count, j - i) return max_count ```

Each pointer only moves forward across $2n$ entries, so the sweep is $O(n)$; the sort dominates at $O(n\log n)$.

Answer: $O(n\log n)$ via angular sort + $+2\pi$ un-wrapping + width-$\alpha$ sliding window; the max window size is the answer. Examples give $2$ and $3$.