Description
You are given n points in 3D space.
For each point (x,y,z)(x,y,z)(x,y,z) (in double precision), its distance to the origin is
Print the 1-based index (i.e., counting from 1) of the point that is the third closest to the origin.
Important: n can be very large, so you should not store all points before deciding. Process the input in a streaming fashion.
If multiple points have exactly the same distance, the one with the smaller index is considered closer.
Input
-
The first line contains an integer n (3 ≤ n ≤ 1_000_000)
-
Each of the next n lines contains three real numbers x y z (double), representing one point.
Output
Print a single integer — the index (1-based) of the point that is the third closest to the origin.