Algoritmo para cubrir el número máximo de puntos con un círculo de radio dado
Imaginemos que tenemos un avión con algunos puntos. También tenemos un círculo de radio dado.
Necesito un algoritmo que determine tal posición del círculo que cubra el máximo número posible de puntos. Por supuesto, hay muchas de esas posiciones, por lo que el algoritmo debería devolver una de ellas.
La precisión no es importante y el algoritmo puede cometer pequeños errores.
Aquí hay una imagen de ejemplo:
Entrada:
int n
(n <= 50) - número de puntos;
float x[n]
yfloat y[n]
- matrices con coordenadas de puntos X e Y;
float r
- radio del círculo.
Salida:
float cx
yfloat cy
- coordenadas del centro del círculo
No se requiere la velocidad del rayo del algoritmo, pero no debería ser demasiado lento (porque conozco algunas soluciones lentas para esta situación).
Se prefiere el código C ++, pero no es obligatorio.