Es tan simple pero aún no puedo resolverlo. Dados dos rectángulos con lados x, y y a, b respectivamente. Determina la máxima área común posible de los dos.
Respuesta
¿Demasiados anuncios?
Podemos asumir sin pérdida de generalidad que $a \ge b$ y $x \ge y$, lo que reduce los casos posibles a seis:
$$ a \ge b \ge x \ge y \;\;\;\; x \ge y \ge a \ge b $$
$$ a \ge x \ge b \ge y \;\;\;\; x \ge a \ge y \ge b $$
$$ a \ge x \ge y \ge b \;\;\;\; x \ge a \ge b \ge y $$
Los primeros cuatro casos son triviales en que un rectángulo se puede colocar dentro del otro, y los tres casos de la derecha son simétricos con los tres casos de la izquierda intercambiando los roles de $a, b$ y $x, y$. Por lo tanto, basta con resolver el caso inferior izquierdo.
Nótese que para simplificar usamos desigualdades débiles, por lo que los casos presentados no son disjuntos. Sin embargo, pares de rectángulos que cumplen más de un caso pueden tratarse como casos límite de las respectivas clasificaciones utilizando desigualdades estrictas. Por ejemplo, nuestro subcaso $ a = x \ge y \ge b $ es también un caso límite de uno de los casos triviales, en que las anchuras iguales permiten que un rectángulo quepa justo dentro del otro.
Tomemos el rectángulo $x, y$ como centrado en el origen, con lados paralelos a los ejes cartesianos como es habitual, es decir, con vértices $(\pm x/2, \pm y/2)$. Buscamos entonces un centro y una rotación del rectángulo $a, b$ "más ancho pero más corto" para maximizar el área de su superposición con el rectángulo "fijo".
La ubicación que maximiza no será generalmente única. Por ejemplo, consideremos el caso de un rectángulo móvil "muy ancho", con $a \gt \sqrt{x^2 + y^2}$. Entonces, para cualquier ubicación que maximice, el rectángulo móvil puede ser "deslizado" de alguna manera a lo largo de su anchura al menos alguna distancia positiva sin reducir el área de superposición.
La discusión se simplificará si restringimos la atención a ubicar el centro del rectángulo móvil también en el origen. Esta restricción es plausible, pero no he desarrollado completamente los detalles de una prueba. Una idea para una prueba es la siguiente: Para una rotación fija (orientación) del rectángulo móvil, mostrar que el área de superposición es una función unimodal de la ubicación de su centro. Al reflejar a través del origen (que esencialmente preserva la orientación del rectángulo móvil, debido a la simetría), el área máxima de superposición se obtiene ubicando el centro en el origen.
Ahora, el problema es una maximización unidimensional bastante simple. Para $a$ suficientemente grande, la orientación óptima coloca el rectángulo "más ancho pero más corto" paralelo a una diagonal del rectángulo fijo. En el límite $a = x$, la orientación coloca las anchuras de los rectángulos en paralelo. Para los casos intermedios $x \lt a \lt \sqrt{x^2 + y^2}$ esperamos variar la orientación, de modo que el aumento de la anchura $a$ provoca la rotación desde la alineación "horizontal" hasta la "diagonal".
