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 | 
