K Closest Points to Origin

Medium

heapquickselectgeometry

Given points on a plane, return the k points closest to the origin by Euclidean distance, ordered by distance (ties: smaller x first, then smaller y).

Input

Line 1: two integers n 2 (n points, 2 coordinates each)
Next n lines: x y of each point
Last line: integer k

Output: k lines, each x y.

Example 1

Input:

Output:

-2 2

√8 < √10.

Example 2

Input:

Output:

3 3
-2 4

Constraints

1 ≤ k ≤ n ≤ 10^4
-10^4 ≤ coordinates ≤ 10^4

Watch a video walkthrough

Run your code against the sample tests, or Submit to run the full suite.

Problems

K Closest Points to Origin

Medium

heapquickselectgeometry

Given points on a plane, return the k points closest to the origin by Euclidean distance, ordered by distance (ties: smaller x first, then smaller y).

Input

Line 1: two integers n 2 (n points, 2 coordinates each)
Next n lines: x y of each point
Last line: integer k

Output: k lines, each x y.

Example 1

Input:

Output:

-2 2

√8 < √10.

Example 2

Input:

Output:

3 3
-2 4

Constraints

1 ≤ k ≤ n ≤ 10^4
-10^4 ≤ coordinates ≤ 10^4

Watch a video walkthrough

Run your code against the sample tests, or Submit to run the full suite.