Nombre Password [ Regístrate ]

Televoz (OIE 6 - 2002)

 

El gobierno de cierto país africano ha decidido dar servicio telefónico a los poblados de cierta zona de la sabana. Su ministerio de comunicaciones ha encargado a la empresa Televoz el diseño de un proyecto que se ajuste a su apretado presupuesto. La idea de Televoz es la de situar estratégicamente una serie de antenas de telefonía móvil de modo que, con el menor número de ellas, se dé cobertura a todos los poblados. En este territorio la cobertura depende sólo de la distancia a la antena, pues no existen accidentes orográficos ni otro tipo de obstáculos que creen zonas de sombra.

Objetivo

Calcula cuál sería el número mínimo de antenas con las que se podría resolver el problema. Para ello dispondrás de las coordenadas rectangulares (en Km) de los poblados, extraídas del mapa enviado por el ministerio, y conocerás el alcance (también en Km) del tipo de antenas que Televoz pretende instalar.

Por si te fuese de utilidad te recordamos que la fórmula que da la distancia, d, entre dos puntos, (x1,y1) y (x2,y2), es:

 

 

Entrada

Los datos del problema los encontrarás en un archivo de texto (ASCII) con nombre "TELE.DAT", que tendrá la siguiente estructura:

- La primera línea contendrá el radio de alcance, R, de las antenas. ( 0 < R < 100).
- La segunda línea del archivo contendrá el número, N, de poblaciones que aparecen en el mapa. (0 < N <= 30).
- Las N líneas siguientes contendrán, cada una de ellas, las coordenadas (X,Y) sobre el mapa de cada una de las poblaciones. (0 <= X <= 300, 0 <= Y <= 300). En cada una de ellas, las dos coordenadas irán separadas por un único espacio en blanco.
- Para simplificar, y puesto que la tolerancia de las especificaciones de las antenas así lo permite, todos los datos de entrada se darán con números enteros.

Salida

El resultado se grabará en un archivo de texto (ASCII) de nombre "TELE.RES", que contendrá una sola línea con el número de antenas necesarias para dar cobertura a todos los poblados. (Nótese que un poblado se considera cubierto por una antena si la distancia entre ellos es menor o igual que R). En este archivo no habrá ningún espacio en blanco.

Ejemplo de entrada

5
7
0 1
2 3
3 1
9 4
11 6
12 3
14 5

Ejemplo de salida

2



© (2001-2008) ALGORITMIA.NET - Política de privacidad