El problema de final feliz (en realidad un teorema) establece que
Cualquier conjunto de cinco puntos en el plano en posición general tiene un subconjunto de cuatro puntos que forman los vértices de un cuadrilátero convexo.
El problema fue llamado así por Paul Erdős cuando dos matemáticos que trabajaron por primera vez en el problema, Ester Klein y George Szekeres, se comprometieron y posteriormente se casaron.
Aclaraciones:
- La posición general aquí significa que no hay tres puntos colineales.
El cuadrilátero formado por los cuatro vértices siempre se considerará que no se cruza, independientemente del orden de los puntos. Por ejemplo, teniendo en cuenta los cuatro puntos
[1 1]
,[1 2]
,[2 1]
,[2 2]
el cuadrilátero intención es la plaza, no la corbata de lazo:Un cuadrilátero que no se cruza es convexo si ningún ángulo interior excede los 180 grados; o equivalente si ambas diagonales se encuentran dentro del cuadrilátero.
El reto
Dados 5 puntos con coordenadas enteras positivas, genera 4 de esos puntos que forman un cuadrilátero convexo.
Reglas
Si hay varias soluciones (es decir, varios conjuntos de 4 puntos), puede optar constantemente por generar uno o todos.
Los formatos de entrada y salida son flexibles como de costumbre (matrices, listas, lista de listas, cadenas con separadores razonables, etc.).
Código de golf, menos bytes gana.
Casos de prueba
Entrada:
[6 8] [1 10] [6 6] [5 9] [8 10]
Solo hay una salida posible:
[6 8] [1 10] [6 6] [5 9]
Entrada:
[3 8] [7 5] [6 9] [7 8] [5 1]
Hay cinco soluciones:
[3 8] [7 5] [6 9] [7 8] [3 8] [7 5] [6 9] [5 1] [3 8] [7 5] [7 8] [5 1] [3 8] [6 9] [7 8] [5 1] [7 5] [6 9] [7 8] [5 1]
Entrada:
[4 8] [1 9] [9 9] [10 2] [1 6]
Hay tres soluciones:
[4 8] [1 9] [10 2] [1 6] [4 8] [9 9] [10 2] [1 6] [1 9] [9 9] [10 2] [1 6]
Para ilustrar, aquí están las tres soluciones para este caso:
Respuestas:
CJam,
373432 bytesNo estoy seguro de si
:-V
es lo suficientemente feliz, pero como señala K Zhang, está=}
el final. :)Esto solo imprime una solución porque eliminar duplicados sería más costoso.
Pruébalo aquí.
Explicación
La idea es bastante simple. Generamos todos los cuadriláteros posibles (incluidos todos los ordenamientos de los puntos) y luego solo seleccionamos los convexos. Probamos la convexidad observando cada par de bordes y verificando que todos estén girando en la misma dirección.
El sentido de giro se puede obtener con bastante facilidad de un producto de punto. Si toma los tres puntos consecutivos en un cuadrilátero, y dibuja líneas del primero al segundo, y del primero al tercero, y luego proyecta el último en la perpendicular del primero ... obtendrá un número cuyo signo le indica si estos tres puntos giran a la izquierda o a la derecha. (Probablemente debería agregar un diagrama para esto). Esta "proyección sobre la perpendicular" suena bastante complicada, pero en realidad solo significa que invertimos uno de los dos vectores y restamos los componentes después de la multiplicación en lugar de sumarlos. Así que aquí está el código ...
fuente
!}
también podría considerarse un guiñoMATLAB, 67 bytes
La entrada tiene la forma de una matriz 2D donde las columnas son X e Y respectivamente:
Todos los conjuntos de 4 puntos que crean cuadriláteros convexos se muestran en el mismo formato.
Aquí hay una demostración que está ligeramente modificada para funcionar con Octave
Explicación
Esta solución toma todos los subconjuntos de 4 puntos de la entrada (el orden no importa). Para ello, creamos la matriz identidad y negar que:
~eye(5)
. Recorremos las columnas de esta matriz yk
(el índice del ciclo) es una matriz lógica que especifica cuál de los 4 puntos a considerar. Luego usamos esto para tomar estos 4 puntos XY de la entrada (I(k,:)
).Luego calculamos el casco convexo de estos 4 puntos (
convhull
). La salida deconvhull
son los índices de la entrada que se corresponden con los puntos que conforman el casco convexo (con el primer índice duplicado para cerrar el casco).Para un cuadrilátero convexo, los cuatro puntos serán parte del casco convexo de los mismos puntos (
nnz(convhull(points)) > 4
). Si detectamos que este es el caso, mostramos los puntos que se utilizaron para esta iteración en particular.fuente
Javascript (ES6),
306293283 bytesExplicacion :
La función
c
calcula el producto cruzado del vector entre 3 puntos adyacentes del polígono y devuelve 1 si es positivo y 0 de lo contrario (nota: el producto cruzado no puede ser cero ya que los puntos no pueden ser co-lineales).La función
k
yj
genera todas las permutaciones cíclicas (ignorando invertir el orden) de la matriz de entrada.Luego se llama a la función 'i' para cada permutación cíclica para calcular la suma de la función
c
para cada una de las 4 tripletas de coordenadas adyacentes. Si todos los productos cruzados tienen el mismo signo, todos serán 0 o 1 y totalizarán 0 (módulo 4) y el polígono es cóncavo y se inserta en la matriz de salida. Si algún triplete tiene un signo diferente, el total será distinto de cero (módulo 4) y el polígono es convexo.La función
f
se usa para inicializar la matriz de salida y luego llamar a las funciones anteriores antes de devolver la salida.Pruebas :
Editar :
También puede manejar puntos co-lineales usando la versión original y cambiando las dos primeras líneas a:
Sin embargo, dado que ese caso se excluye específicamente en la pregunta, los caracteres adicionales no son necesarios.
fuente
Mathematica
10596 bytesSelect[#~Subsets~{4},f@#&]&
selecciona, de una lista de (5) puntos, aquellos subconjuntos de 4 puntos que satisfacenf
.f
se satisface cuando cada punto, de los 4 puntos en un conjunto, se encuentra enRegionBoundary
elConvexHull
de los 4 puntos.Casos de prueba
1. Veamos los 5 cascos convexos de subconjuntos (cada uno de 4 puntos) de {{6, 8}, {1, 10}, {6, 6}, {5, 9}, {8, 10}} .
{{{6, 8}, {1, 10}, {6, 6}, {5, 9}}}
{{6, 8}, {1, 10}, {6, 6}, {5, 9}} es la única solución; cada uno de los cuatro puntos sirve como vértice del casco convexo (de los mismos 4 puntos).
{{6, 8}, {1, 10}, {6, 6}, {8, 10}} no es una solución; El casco convexo tiene solo 3 vértices. {6, 8} se encuentra dentro del casco.
Los subconjuntos restantes tampoco son soluciones:
2. {{4, 8}, {1, 9}, {9, 9}, {10, 2}, {1, 6}} tiene tres soluciones.
{
{{4, 8}, {1, 9}, {10, 2}, {1, 6}},
{{4, 8}, {9, 9}, {10, 2}, {1, 6 }},
{{1, 9}, {9, 9}, {10, 2}, {1, 6}}
}
3. {{3, 8}, {7, 5}, {6, 9}, {7, 8}, {5, 1}} tiene 5 soluciones.
{
{{3, 8}, {7, 5}, {6, 9}, {7, 8}},
{{3, 8}, {7, 5}, {6, 9}, {5, 1 }},
{{3, 8}, {7, 5}, {7, 8}, {5, 1}},
{{3, 8}, {6, 9}, {7, 8}, {5 , 1}},
{{7, 5}, {6, 9}, {7, 8}, {5, 1}}
}
Tenga en cuenta que cada uno de los cinco puntos se encuentra en el límite del casco convexo de todos los puntos.
Si se elimina cualquiera de los puntos, los 4 puntos restantes serán vértices del casco convexo reducido.
fuente