Estás malinterpretando el problema. Los cuadrados deben ser todos del mismo tamaño, no su área que se superpone al polígono.
Esta oración debería haber sido aclarada o modificada:
“Todos los mapas deben ser perfectamente cuadrados y deben cubrir la misma cantidad de área en el cañón”.
Aquí la especificación significa el área que ocupa el cuadrado y no el área de la intersección del cuadrado y el polígono. Estoy de acuerdo en que esta versión es un problema mucho más difícil. Otras áreas de la especificación aclaran esto. (Tal como la especificación de salida) Por ejemplo, el valor final calculado es la longitud lateral de cada cuadrado incluido en la portada.
- ¿Cuál es la diferencia entre la recursión normal y la recursiva de la cola con ejemplos?
- ¿Cuáles son los libros de Ciencias de la Computación (Algoritmo) que recomendará un topcoder?
- ¿Cómo agrupa Google News las historias?
- Cómo acceder a la raíz de un árbol binario si está almacenado en una estructura
- Cómo usar la ordenación por inserción para ordenar una matriz 2D en Java
La solución a este problema es simplemente realizar una búsqueda binaria sobre la longitud del lado y determinar si los cuadrados de esa longitud lateral pueden cubrir el polígono. La longitud lateral más pequeña que cubre con éxito la forma es la respuesta.
Para determinar la cobertura del cuadrado, puede determinar de forma única 8 posibilidades para colocar un cuadrado en el borde de un polígono. (Este punto debe cubrirse en algún rectángulo. ¿Por qué no ahora?) Por ejemplo, resolveremos un lado. Llamemos a este valor lateral de un cuadrado, dictado por la búsqueda binaria, s . Coloque una línea vertical a través del punto más a la izquierda en el polígono. Ahora compensa esta línea en la dirección x positiva por s . Corta el polígono por esta línea. Tienes dos opciones. Coloque el tamaño s x s cuadrado en la parte superior de esta forma o en la parte inferior. Hacer esto por un lado te da dos de las 8 posibilidades. Entonces, simplemente generaliza este algoritmo para los otros 4 lados.
Cuando corta un fragmento del polígono de esta manera, puede resolver el problema restante de forma recursiva en el polígono restante. (El último cuadrado se puede resolver simplemente verificando si todos los puntos caben en un cuadro sxs)
Para facilitar la implementación, solo tiene que probar si los lados del polígono pueden estar cubiertos por los tres cuadrados. Esto es suficiente porque no hay forma de formar un polígono con un agujero a través de la unión del área de cuadrados alineados de tres ejes. Por lo tanto, cualquier cubierta que cubra las líneas de límite también debe cubrir el área interna.
