Como roadie de la banda, tienes que empacar el camión. Su programa colocará los paquetes para que quepan en la altura más pequeña.
Un camión mal embalado
Reglas
Los paquetes pueden rotarse a través de múltiplos de 90 grados. Los paquetes pueden tocar pero no deben superponerse.
El resultado es la imagen reempaquetada (para archivar o stdout). Su programa puede usar cualquier formato de imagen ráster de entrada o salida.
Su programa debe aceptar cualquier cantidad de paquetes de varias formas en imágenes de hasta 4000x4000 píxeles. No debe estar codificado para esta imagen de prueba. Si sospecho que algún envío se debe adaptar a esta imagen específica, me reservo el derecho de reemplazarlo por una nueva imagen de prueba.
Puntuación
Su puntaje es la altura más pequeña de un rectángulo que contendrá su disposición (el ancho es el ancho del rectángulo de entrada). En caso de empate, la primera entrada gana.
Las lagunas estándar están prohibidas como de costumbre.
fuente
Respuestas:
Lengua: Java
Puntuación:
555533Solo intenté forzar una solución por fuerza bruta iterando sobre las formas en orden de área decreciente (perímetro en caso de empate) y probando todas las posibilidades de empaque hasta que se encuentre un empaque válido para esa forma, en cuyo punto se fija la posición de la forma. y el algoritmo pasa a la siguiente forma. Con el fin de mejorar la calidad del resultado cuando se busca un embalaje válido, primero se intentan todas las posiciones posibles con la forma girada de manera que sea más alta que ancha.
Nota: esto supone que las imágenes de entrada tienen todas las formas separadas por espacios en blanco. Toma el ancho máximo de la salida como primer argumento y una lista de imágenes de forma como los otros argumentos (cada imagen de forma puede tener una o más formas separadas por al menos una línea de píxeles blancos)
La solución que esto produce (toma aproximadamente
4 minutos y30 segundos en mi máquina) es:Al ver esta imagen, parece que el resultado puede mejorarse iterando sobre todas las formas después del empaquetado e intentando moverlas un poco hacia arriba. Podría intentar hacer eso más tarde.fuente