Dada una lista de coordenadas enteras, encuentre el área del polígono convexo más grande que puede construir de la lista de tal manera que:
- cada vértice está en la lista
- Ningún elemento de la lista está contenido dentro del polígono.
Ejemplo:
(0, 0) (8, 0) (0, 1) (3, 1) (7, 1) (1, 2) (5, 2) (9, 2) (2, 3) (5, 3) (7, 3) (3, 4) (5, 5) (11, 5)
Visualizado:
o o
o o o
o o o
o o o
o
o o
El polígono convexo más grande que puede hacer de esto es este:
o
o o
o o
o o
o
o
Con una superficie de 12.
Puede tomar la lista de coordenadas en cualquier formato razonable y debe generar (de manera apropiada para el idioma que elija) el área del polígono convexo más grande, redondeada a no menos de 2 dígitos después del punto decimal.
Además, debe emplear algún tipo de algoritmo, y no simplemente fuerza bruta en todos los subconjuntos de puntos. Para hacer cumplir esto, su programa debe resolver una lista de 50 vértices en menos de un minuto en una PC moderna.
El código más corto en bytes gana.
Respuestas:
Javascript ES6, 738 bytes
Aquí hay una versión ES5 o menos que debería funcionar en la mayoría de los navegadores y nodos sin ajustar: 827 bytes
El código devuelve una función anónima. Como parámetro, toma una serie de puntos, como
[[0,1],[2,3],[4,5]]
. Para usarlo, puede colocarlovar f=
antes, o si desea usarlo desde la línea de comando, agregar(process.argv[2].replace(/ /g,'').slice(1,-1).split(')(').map((x)=>x.split(',')))
al final y llamarlo comonode convpol.js '(1,2)(3,4)(5,6)'
Gracias por el reto! Como no hay implementación de referencia, no puedo probar que esto sea correcto, pero es consistente al menos para las permutaciones de la lista de puntos. Casi no pensé que esto iba a funcionar, ya que las versiones con código de depuración, incluso deshabilitadas, eran demasiado lentas con un aumento exponencial del tiempo. Decidí jugar golf de todos modos, y me complació ver que se redujo a menos de 2 segundos por 50 puntos en mi máquina. Puede calcular aproximadamente 130 puntos en 1 minuto.
El algoritmo es similar al escaneo de Graham , excepto que tiene que buscar cascos convexos vacíos en todas partes.
Explicación
Aquí hay una descripción general de alto nivel de cómo funciona el algoritmo. La esencia de este algoritmo es solo buscar bucles convexos en sentido antihorario que no encierren un punto. El procedimiento es algo como esto:
Además, como optimización, registramos el par inicial de la cadena como verificado, por lo que cualquier búsqueda posterior al ver este par en cualquier parte de la cadena puede dejar de buscar inmediatamente, ya que el polígono más grande con este par ya se ha encontrado.
Este algoritmo nunca debería encontrar un polígono dos veces, y lo he verificado experimentalmente.
fuente
===
y!==
con==
y!=
, pero no podría estar seguro sin comprender su código ...(x,i)=>p.i==i
(13 caracteres) es bastante más largo quex=>p===x
(8 caracteres) incluso después de la optimización.