Vacas Claustrofóbicas


Submit solution

Points: 100 (partial)
Time limit: 1.0s
Memory limit: 256M

Author:
Problem type
Allowed languages
Ada, BrainF***, C, C#, C++, Dart, Go, Java, JS, Kotlin, Pascal, Prolog, Swift, VB

El Granjero Juan ha adquirido un conjunto de N (1 \leq N \leq 2000) vacas quisquillosas que están numeradas convenientemente 1...N. Ellas realmente odian estar cerca de otras vacas. Un montón.

GJ ha registrado las coordenadas enteras X_i, Y_i de cada vaca (1 \leq X_i \leq 100 000; 1 \leq Y_i \leq 100 000).

Entre todas esas vacas, exactamente dos de ellas están más cerca. A GJ le gustaría separarlas un poco. Determine cuáles dos están más cerca e imprima sus números de identificación de vacas (i) en orden numérico.

Por ejemplo, considere este campo de vacas (representado en una cuadricula mecanografiada que tiene proporciones ligeramente diferentes de las que usted podría esperar):

                10 | . . . . . . . 3 . . . . .
                 9 | . 1 . . 2 . . . . . . . .
                 8 | . . . . . . . . . . . . .
                 7 | . . . . . . . . . . 4 . .
                 6 | . . . . . . 9 . . . . . .
                 5 | . 8 . . . . . . . . . . .
                 4 | . . . . . 7 . . . . . . .
                 3 | . . . . . . . . . 5 . . .
                 2 | . . . . . . . . . . . . .
                 1 | . . . . 6 . . . . . . . .
                 0 ---------------------------
                                       1 1 1 1
                   0 1 2 3 4 5 6 7 8 9 0 1 2 3

Una rápida inspección visual muestra que las vacas 7 y 9 son las más cercanas (la distancia entre ellas es sqrt(1×1 + 2×2) = sqrt(5), por lo tanto la salida sería '7 9' en una sola línea (sin las comillas, por supuesto).

Entrada

• Línea 1: Un solo entero N.

• Líneas 2…N+1: La línea i contiene las coordenadas de la vaca i expresadas como dos enteros separados por espacio: X_i y Y_i.

Salida

• Línea 1: Los dos Ids numéricos del par de vacas más cercanas (ordenados).

Ejemplo de Entrada

9
2 9
5 9
8 10
11 7
10 3
5 1
6 4
2 5
7 6

Ejemplo de Salida

7 9

Comments

There are no comments at the moment.