Vacas Claustrofóbicas
El Granjero Juan ha adquirido un conjunto de vacas quisquillosas que están numeradas convenientemente . Ellas realmente odian estar cerca de otras vacas. Un montón.
GJ ha registrado las coordenadas enteras , de cada vaca .
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 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 y 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 .
• Líneas 2…N+1: La línea contiene las coordenadas de la vaca expresadas como dos enteros separados por espacio: y .
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