Select the k Points Nearest the Origin with Distance and Coordinate Tie-Breaks

Given a list of points on a 2D integer grid and an integer `k`, return the `k` points that are closest to the origin `(0, 0)`, listed in a fixed order. Closeness is measured by Euclidean distance. Because only comparisons matter, two points can be compared by their squared distances $x^2 + y^2$, which are exact integers. ### Function Signature ```python def k_nearest_to_origin(points: list[list[int]], k: int) -> list[list[int]]: ``` ### Rules - Each element of `points` is a pair `[x, y]`. - Rank every point by the key `(x*x + y*y, x, y)` in ascending order: nearer points come first, a tie in distance is broken by the smaller `x`, and a remaining tie by the smaller `y`. - Return the first `k` points of that ranking, each as `[x, y]`, in ranking order. This makes the answer unique. - The same coordinates may appear more than once in `points`. Each occurrence is a separate point and counts toward `k`. ### Constraints - `1 <= k <= len(points) <= 10^4` - `-10^4 <= x, y <= 10^4` - Squared distances are at most `2 * 10^8`, which fits in a signed 32-bit integer. ### Examples **Example 1** ```text Input: points = [[2, 3], [-1, -2]], k = 1 Output: [[-1, -2]] ``` The squared distances are 13 and 5, so `[-1, -2]` is nearer. **Example 2** ```text Input: points = [[4, 1], [-3, 3], [0, -4], [2, 5]], k = 2 Output: [[0, -4], [4, 1]] ``` The squared distances are 17, 18, 16 and 29. The two smallest are 16 for `[0, -4]` and 17 for `[4, 1]`, returned nearest first. **Example 3** ```text Input: points = [[1, 0], [2, 2], [0, 1], [-1, 0], [0, 1]], k = 3 Output: [[-1, 0], [0, 1], [0, 1]] ``` Four points have squared distance 1. Ordered by `x` and then `y` they are `[-1, 0]`, `[0, 1]`, `[0, 1]`, `[1, 0]`; the first three are returned, and the duplicate `[0, 1]` appears twice.