Estación Base.
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 . El rango de comunicación de cada estación base es un cuadrado centrado en con la línea inferior de paralela a , y la longitud de un lado de es llamado el ancho de comunicación de . 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 coincide con el eje de las y la ubicación de cada edificio está dada por dos enteros los cuales representan las coordenadas , respectivamente. Todos los edificios tienen diferente localización.
En la siguiente figura,
1) La localización de la primera estación base es y su rango de comunicación corresponde al cuadrado con ancho de comunicación e incluye edificios.
2) La localización de la segunda estación base es , y su rango de comunicación corresponde al cuadrado con ancho de comunicación e incluye dos edificios.
3) La localización de la tercera estación base es , y su rango de comunicación corresponde al cuadrado con ancho de comunicación e incluye a dos edificios.
Entrada
La entrada contiene el número , y cada línea de las próximas líneas contiene las coordenadas de la y las coordenadas de la separadas por un espacio. El valor absoluto de las coordenadas y es un entero el cual no es mayor que 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
Hola, en el gráfico en el eje x de los negativos omitieron el -1