Le dan N puntos y desea trazar una línea tal que los puntos máximos se encuentren en la línea. ¿Cuál es la forma más eficiente de encontrar el número máximo de puntos?
Respuesta
¿Demasiados anuncios?
user2566092
Puntos
19546
El truco se llama dualidad. Asigna un punto$(m,b)$ a una línea que tiene esa pendiente e intersección, y la transformación inversa es obvia para asignar una línea a un punto. Entonces calcula la disposición de las líneas, colocando un cuadro delimitador lo suficientemente grande alrededor del exterior para que tenga un gráfico plano finito. Luego encuentras el punto de intersección que tiene la mayor cantidad de líneas que pasan por él, y listo. Tenga en cuenta que el número de puntos de intersección es lineal porque el gráfico es plano.
