Estación Base.


Submit solution

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

Author:
Problem type
Allowed languages
C, C++, Java, Pascal, Python, VB

La empresa de comunicación inalámbrica de los azucareros del centro incluirá los edificios en el rango de comunicación estableciendo varias estaciones base a lo largo de una línea recta de comunicación horizontal L. El rango de comunicación de cada estación base B es un cuadrado S centrado en B con la línea inferior de S paralela a L, y la longitud de un lado de S es llamado el ancho de comunicación de B. El costo total del establecimiento de las estaciones base es la suma de los anchos de comunicación de todas las estaciones sin considerar el número de estaciones bases.

Dada las ubicaciones de los edificios en el plano, escriba un programa el cual determine el costo mínimo para el establecimiento de las estaciones base con el propósito de incluir todos los edificios dentro del rango de comunicación de las estaciones base.

La línea de comunicación L coincide con el eje de las X y la ubicación de cada edificio está dada por dos enteros los cuales representan las coordenadas X, Y respectivamente. Todos los edificios tienen diferente localización.

En la siguiente figura,

1) La localización de la primera estación base es (-3,0) y su rango de comunicación corresponde al cuadrado con ancho de comunicación 4 e incluye 3 edificios.

2) La localización de la segunda estación base es (2,0), y su rango de comunicación corresponde al cuadrado con ancho de comunicación 2 e incluye dos edificios.

3) La localización de la tercera estación base es (6.5, 0), y su rango de comunicación corresponde al cuadrado con ancho de comunicación 3 e incluye a dos edificios.

Entrada

La entrada contiene el número N (1 \leq N \leq 10, 000), y cada línea de las próximas N líneas contiene las coordenadas de la X y las coordenadas de la Y separadas por un espacio. El valor absoluto de las coordenadas X y Y es un entero el cual no es mayor que 1,000,000 respectivamente.

Salida

La salida contiene en la primera línea el costo mínimo (la suma total de los anchos de comunicación) de las estaciones base.

Ejemplo de Entrada

7                       
-2 -1
-4 -1
0 2
3 1
5 1 
1 -1
8 -1

Ejemplo de Salida

9

Comments


  • 0
    NoelJosue  commented on May 16, 2022, 7:32 p.m.

    Hola, en el gráfico en el eje x de los negativos omitieron el -1