Найближчі точки
Limits: 2 sec., 256 MiB
На площині знаходиться nn точок пронумерованих від 11 до nn з координатами (xi,yi)(xi,yi).
Відстань між точками з індексами ii та jj визначається як dist(i,j)=min(|xi−xj|,|yi−yj|)dist(i,j)=min(|xi−xj|,|yi−yj|).
Знайдіть пару точок з найменшою можливою відстанню.
Input
У першому рядку nn — кількість точок на площині. В наступних nn рядках дано по 2 цілі числа xixi та yiyi — координати ii-ої точки.
Output
В одному рядку виведіть через пропуск два цілі числа ii та jj — індекси точок між якими найменша відстань.
Якщо таких пар точок більш ніж одна, то знайдіть пару для якої мінімізується i+ji+j.
Якщо і таких пар декілька, то серед них знайдіть пару з мінімальним ii.
Constraints
2≤n≤1000002≤n≤100000,
−109≤xi,yi≤109−109≤xi,yi≤109.
Samples
Input (stdin) | Output (stdout) |
---|---|
2 1 1 2 2 | 1 2 |
Input (stdin) | Output (stdout) |
---|---|
4 3 3 2 0 0 2 0 0 | 2 4 |
Source: The Algo Battles 2023 - Етап 2