Claustrophobic Cows

Interview

Time limit1sMemory limit128 MB

Summary

Given up to 2000 points, find the unique pair with the smallest Euclidean distance and print their ids in increasing order.

Level: Medium6 of 10
Topics: Geometry, Divide and conquer, Sorting, Brute force
Solved: No attempts yet

Problem

Farmer John's $N$ cows are numbered $1$ through $N$ , and they really hate being too close to one another.

Each cow $i$ is located at integer coordinates $(X_i, Y_i)$ . The distance between two cows is the Euclidean distance $\sqrt{(X_i - X_j)^2 + (Y_i - Y_j)^2}$ .

Among all pairs of cows, exactly one pair is closest together. Find these two closest cows and print their id numbers in increasing order.

Constraints

$2 \le N \le 2000$
$1 \le X_i \le 100000$
$1 \le Y_i \le 100000$

Input

Line 1: A single integer $N$ .
Lines 2 to $N+1$ : Line $i$ contains the coordinates of cow $i$ as two space-separated integers $X_i$ and $Y_i$ .

Output

Line 1: The ids of the two closest cows, in increasing order, separated by a single space.

Examples1

Example 1

Input

Expected output

7 9