F - Regular Triangle Inside a Rectangle Editorial by en_translator
In the optimal fit, we may assume that the regular triangle and the rectangle shares at least one vertex.
Proof
Consider the topmost, bottommost, rightmost, and leftmost point on the regular triangle; in fact, there is at least one such vertex each. Also, a vertex cannot be simultaneously be the topmost and bottommost, or rightmost and leftmost, so the triangle always satisfies at least one of the following statements:
- There exists a vertex that is the topmost and rightmost point on the triangle.
- There exists a vertex that is the topmost and leftmost point on the triangle.
- There exists a vertex that is the bottommost and rightmost point on the triangle.
- There exists a vertex that is the bottommost and leftmost point on the triangle.
For example, if the first statement hold, then we can shift the triangle so that that vertex coincides with at least one of the vertices of the rectangle, so we can assume that the optimal fit satisfies this assumption.
How can we determine if a regular triangle of side \(l\) can be drawn in the interior of the rectangle? (If we can do so, we can solve this problem by doing binary search for the maximum side length \(l\) that can be drawn in the rectangle.)
With appropriate rotation and inversion, we assume that the bottom-left vertex of the rectangle coincide with a vertex of the triangle. Let \(\theta\) be the angle between the lower edges of the rectangle and the triangle. Then the angle between the lower edge of the rectangle and the upper edge of the triangle is \(\theta + 60^\circ\). Also, since \(\theta \geq 0^\circ\) and \(\theta + 60^\circ \leq 90 ^ \circ\), we have \(0^\circ \leq \theta \leq 30^\circ\).
Here, the width of the triangle is \(l \cos \theta\) and the height is \(l \sin \theta\), so we need to find if there is a \(\theta\) such that \(\cos \theta \leq \frac{B}{l}, \sin\theta \leq \frac{A}{l}, 0^\circ \leq \theta \leq 30^\circ\).
(within \(0^\circ \leq \theta \leq 30^\circ\), ) \(\cos \theta\) decreases and \(\sin\theta\) increases as \(\theta\) increases. Thus, we may find the minimum \(\theta\) such that \(\cos \theta \leq \frac{B}{l}\) within the range value (using binary search or by evaluating \(\cos^{-1} \theta\) depending on whether \(\frac{B}{l}\) is between \(0\) and \(\frac{\sqrt{3}}{2}\)), and check if this satisfies \(\sin \theta \leq \frac{A}{l}\).
posted:
last update: