Distancias Extrañas

Points: 100 (partial)

Time limit: 2.0s

Memory limit: 512M

Authors:

ToOma_KFP, wizard98

Problem types

Allowed languages

Ada, BrainF***, C, C#, C++, Dart, Go, Java, JS, Kotlin, Lua, Pascal, Prolog, Python, Swift, VB

Se dan $1 \le N \le 10^5$ $1 \leq N \leq 10^{5}$ puntos en el plano cartesiano. Definimos la distancia entre dos puntos $(x1,y1)$ $(x 1, y 1)$ y $(x2,y2)$ $(x 2, y 2)$ como $m i n (∣ x 1 - x 2 ∣, ∣ y 1 - y 2 ∣)$ . Calcule el valor de la $K$ $K$ -ésima distancia entre cada par de puntos, con $1 \le K \le \frac{N \cdot (N-1)}{2}$ $1 \leq K \leq \frac{N \cdot (N - 1)}{2}$ .

Entrada

La primera línea contiene dos enteros $N$ $N$ y $K$ $K$ .

Cada una de las siguientes $N$ $N$ líneas contiene dos valores enteros que representan las coordenadas de los puntos, las coordenadas de los puntos son enteros positivos entre $1..10^5$ $1. {.10}^{5}$

Salida

La salida debe consistir en un único valor entero que represente el valor de la distancia $K$ $K$ -ésima.

Ejemplo de Entrada

Copy

Ejemplo de Salida

Copy

Explicación del Ejemplo

$dist(1,2)=3$ $d i s t (1, 2) = 3$

$dist(1,3)=0$ $d i s t (1, 3) = 0$

$dist(1,4)=2$ $d i s t (1, 4) = 2$

$dist(2,3)=1$ $d i s t (2, 3) = 1$

$dist(2,4)=1$ $d i s t (2, 4) = 1$

$dist(3,4)=2$ $d i s t (3, 4) = 2$

Distancias ordenadas: $\{0,1,1,2,2,3\}$ ${0, 1, 1, 2, 2, 3}$

Comments

2

smauwl_spike commented on Sept. 7, 2023, 4:45 p.m.

subelealaradio