(0,0), (1,0), (-1,0), (1,1), (-1,1), (-1,-1) y (1-1). Hay 5 segmentos rectos que unen tres de estos puntos. El problema es añadir 2 puntos más para que en lugar de 5 de estos segmentos podamos trazar 10.
#9 Me preguntaba si eso podía contar...
Edit, añado una imagencilla de cómo se cortan las rectas definidas por los puntos del problema, los puntos dato en rojo
#11 Llevo días pensando en decirte que si tomo los 3 puntos iniciales de las rectas como segmento con 3 puntos en la disertación faltan un par de segmentos por contar. Voy a hablar de mi figura en #10 porque los puntos están eqtiquetados y eso ayuda a nombrarlos
Los dados por el problema son A, B, C, D, E, F, y G y tu propuesta es añadir el N y el O
Los segmentos iniciales son
CBD
CAG
DAF
BAE
FEG
Con los puntos añadidos tendremos
COE y DNE en rectas nuevas
DAO, AOF Y DOF en el segmento DAF antiguo
CAN, ANG Y CNG en el antiguo CAG
En total 13 segmentos de 3 puntos alineados. Si no nos gusta el DOF o el CNG tendremos también que eliminar el DAF y el CAG porque tampoco cumplen lo de no tener un punto en medio.
#14 Hola, fantomax. Yo creo que se trata de un problema terminológico. Un segmento es el conjunto de puntos de una recta comprendidos entre dos de sus puntos. Según esta definición, DAF = DOF y CNG = CAG. Me parece que tú estás pensando en ternas de puntos alineadas (y ordenadas y no orientadas), en cuyo caso tendrías razón y hay más.
#10 ¿Se te ocurre un algoritmo para hacer esto de forma más general? Dados n puntos del plano, encontrar las ubicaciones en las que añadir m adicionales de forma que se maximice el número de segmentos que unan ternas de los n + m puntos, supongo que sería el enunciado general.
Me parece que se puede hacer un algoritmo de fuerza bruta sin mucha dificultad, pero quizá sería interesante analizar el coste óptimo, etc.
Comentarios
(0, 1/2) y (0, -1/2)
Pregunta adicional: situar dos puntos adicionales a los originales para obtener 12 segmentos que unan ternas de puntos.
#1 ooops! 11 segmentos, no 12!
#2 No me sale con 11 lineas.
#8 Es que son segmentos distintos, pero pueden ser colineales, ¿no?
#9 Me preguntaba si eso podía contar...
Edit, añado una imagencilla de cómo se cortan las rectas definidas por los puntos del problema, los puntos dato en rojo
#10 espero haber contado bien
#11 Llevo días pensando en decirte que si tomo los 3 puntos iniciales de las rectas como segmento con 3 puntos en la disertación faltan un par de segmentos por contar. Voy a hablar de mi figura en #10 porque los puntos están eqtiquetados y eso ayuda a nombrarlos
Los dados por el problema son A, B, C, D, E, F, y G y tu propuesta es añadir el N y el O
Los segmentos iniciales son
CBD
CAG
DAF
BAE
FEG
Con los puntos añadidos tendremos
COE y DNE en rectas nuevas
DAO, AOF Y DOF en el segmento DAF antiguo
CAN, ANG Y CNG en el antiguo CAG
En total 13 segmentos de 3 puntos alineados. Si no nos gusta el DOF o el CNG tendremos también que eliminar el DAF y el CAG porque tampoco cumplen lo de no tener un punto en medio.
#14 Hola, fantomax. Yo creo que se trata de un problema terminológico. Un segmento es el conjunto de puntos de una recta comprendidos entre dos de sus puntos. Según esta definición, DAF = DOF y CNG = CAG. Me parece que tú estás pensando en ternas de puntos alineadas (y ordenadas y no orientadas), en cuyo caso tendrías razón y hay más.
#10 ¿Se te ocurre un algoritmo para hacer esto de forma más general? Dados n puntos del plano, encontrar las ubicaciones en las que añadir m adicionales de forma que se maximice el número de segmentos que unan ternas de los n + m puntos, supongo que sería el enunciado general.
Me parece que se puede hacer un algoritmo de fuerza bruta sin mucha dificultad, pero quizá sería interesante analizar el coste óptimo, etc.
#12 La verdad, de cosas de algoritmos es mejor preguntar anick_el_cadmio, si es que sigue por aquí.
#1 Tu solución es esta, perfecto.
EDIT; me falta una de las lineas por marcar.
Me intriga la undécima linea.
Con (3,1) y (
3,1) o con (3,-1) y (-3,1) salen 10 segmentos#4 Si no te malinterpreto te refieres a esto y su simétrico. Muy interesante, gracias
#6 yeah
Prolonga segmentos que unan combinaciones de 2 puntos de esos 7, y a ver donde se cortan algunos de esos. Y ya nos cuentas si sale algo