Es claro que el poligono regular divide a la circunferencia en arcos iguales.
Por lo tanto la longitud de los arcos a probar tiene que ser divisor del perimetro de la circunferencia.
Para cada divisor d (que son menores a ~500) , vemos si podemos formar el polígono. Esto no es tan fácil pues no sabemos con que punto 'empezar'. Para resolver esta parte linearizamos el problema: Desplegamos los puntos en una recta, y creamos una copia justo al lado de esta. Esto es: si un punto i estaba en la posición Y[i], también va a haber un punto en la posición Y[i] + C, donde C es el perimetro de la circunferencia.
Ahora observemos que si hay un punto i / Y[i] < C tal que si haciendo saltitos de longitud d solo pasamos por lugares que tienen puntos, entonces ya tenemos nuestro poligono!
Con esta idea podemos diseñar una dinámica, que diga dado un punto i, si haciendo estos saltitos paso solo por lugares que tienen puntos.
dp[i] = true si Y[i]+d>2*C (nos salimos del arreglo)
dp[i] = false si no hay punto en la posicion Y[i]+d
dp[i] = dp[j] si hay un punto j en la posición Y[i]+d
Solo tenemos que chequear si existe un i / Y[i]<C y dp[i]=true. Si se cumple esto se puede formar el poligono con arcos de longitud d y la respuesta sería: N - C/d.
(hay que buscar el menor d que lo cumpla)
0 comentarios: