We will be referring to the primitive picture above. The original rectangle had horizontal side $a$ and vertical side $b$. It was rotated through an angle $\theta$ ($t$ in the picture).
We start with an $a \times b$ rectangle, with horizontal and vertical sides, such that the sides of length $a$ are horizontal. We rotate the rectangle counterclockwise about its center, through an angle $\theta\le \pi/2$.
How much horizontal and vertical space is occupied by the rotated rectangle? (In general, the minimal containing rectangle will not be a square.)
The diagram above can be used to see that the horizontal space occupied is
$$a\cos\theta+b\sin\theta,$$
and that the vertical space occupied is
$$a\sin\theta+b\cos\theta.$$
For suppose that the side labelled $a$ has length $a$, and the side labelled $b$ has length $b$. Then the horizontal side $PR$ of the containing rectangle is made up of two parts. By basic trigonometry, the part $QR$ has length $a\cos\theta$, and the part $PQ$ has length $b\sin\theta$. Add up. A similar argument deals with the vertical side of the containing rectangle.
If we want to fit the rotated rectangle into a square of side $s$, then the least $s$ that will work is given by
$$s=\max(a\cos\theta+b\sin\theta, a\sin\theta+b\cos\theta).$$
If we have a square of fixed side $d$ (in the post, $d=100$), we may want to scale the original rectangle to make the rotated version fit. Let $\lambda$ be the (common) scaling factor of the sides of the original $a\times b$ rectangle that will make the fit in the $d\times d$ square snug horizontally and/or vertically. Then we need
$$\lambda \max(a\cos\theta+b\sin\theta, a\sin\theta+b\cos\theta)=d,$$
and now we can compute $\lambda$.
Comment: The same basic formulas can be used to solve some of the more general problems that you mentioned. We obtained separate formulas for the horizontal and vertical space occupied by the rotated rectangle. Suppose that our target rectangle has given horizontal and vertical sides. We can compute the scaling factor $\lambda_h$ that will give a horizontal fit, and the scaling factor $\lambda_v$ that will give a vertical fit. Then the desired scaling factor for both a horizontal fit and a vertical fit is $\min(\lambda_h, \lambda_v)$. (Here as usual we are working on the assumption that the ratio of the sides must be maintained, so a common scaling factor must be applied to each.)
Let's analyze a single case:
If we want to cover a $6x5$ rectangle with $7$ squares, we first note that each square at most has an area of $30/7$. We also know that for our filling to be optimal, we need to fill at least an axis.
So now we know that we will fill either the $6$ or the $5$ completely. We will first try with the 5. Since the maximal side of our squares is $\sqrt{30/7}$, we now need the smallest integer more than $5/\sqrt{30/7}$, that is equal to $\lceil5/\sqrt{30/7}\rceil=3$
So we would divide the $5$ in $3$ parts $p_x$, so each side will have $5/3$ . If so, I would cover $(5/3)^2*7=19\frac49$ of the thirty squares. If they don't fit vertically, we try with more parts $p_x$, until the squares fit in the other axis. $$\lfloor6/(5/p_x)\rfloor*\lfloor5/(5/p_x)\rfloor=\lfloor6/(5/p_x)\rfloor*p_x\ge7 \,\,\,\,\,\,\,\,\,\, (5/p_x=\text{the actual size of our squares)}$$
Also, since $p_x$ is integer $\lfloor p_x \rfloor =p_x$
If we do the same with the $6$, we get $\lceil6/\sqrt{30/7}\rceil$ again covering $19\frac49$ of the surface. We then do the same as with the $5$ and save it as $p_y$
Let's now recall the formulas we had.
We had an $x∗y$ rectangle and filled it with $N$ squares. We started with $p_x=⌈x/\sqrt{xy/N}⌉$=$⌈\sqrt{Nx/y}⌉$ or $p_y=⌈y/\sqrt{xy/N}⌉=⌈\sqrt{Ny/x}⌉$ and then we made them fit by shrinking them until they fit in the other axis. But we know we want the area maximised, so $Side=max(x/p_x,y/p_y)$.
A better method:
Once we have the start value $p_x=⌈x/\sqrt{xy/N}⌉=⌈\sqrt{Nx/y}⌉$,if it does not fit in the $y$ axis, we need to make it fit in the $y$ axis. For that, we use that
$$a=x/p_x$$
where $a$ is the value of the actual side of our squares.
Then we know that for our side to fit we need to reduce it:
$$S_x=y/(\lceil y/a \rceil)$$
We do the same with $S_y$ and calculate $max(S_x,S_y)$
The advantage of this is that it needs a constant number of operations, the most expensive one being the square root.
Plain, unoptimized C Code
Some multiplications may be reused but for code readability and practical uses this is enough.
Input: values of $x$,$y$, and $n$. Handcoded.
Output: The optimal side of our squares
#include <math.h>
#include <stdio.h>
#define MAX(x,y) (x)>(y)?(x):(y)
int main(){
double x=5, y=6, n=7;//values here
double px=ceil(sqrt(n*x/y));
double sx,sy;
if(floor(px*y/x)*px<n) //does not fit, y/(x/px)=px*y/x
sx=y/ceil(px*y/x);
else
sx= x/px;
double py=ceil(sqrt(n*y/x));
if(floor(py*x/y)*py<n) //does not fit
sy=x/ceil(x*py/y);
else
sy=y/py;
printf("%f",MAX(sx,sy));
return 0;
}
Best Answer
First of all, there may be multiple rectangles that satisfy your conditions, e.g.
However, there is a special case where there is at most only once rectangle, i.e. if you assume that it has to touch both of your boundaries. In such case it is easy to compute it. Place the origin (point $(0,0)$) in the center of the boundary (the center of the circle), and let $(C_x,C_y)$ be the top right boundary corner (the boundary rectangle has size $2C_x \times 2C_y$ ). Let $(x,y)$ be the top right vertex of small rectangle, then it satisfies conditions ($\alpha > 0$ means counterclockwise rotation):
\begin{align*} \left[\begin{matrix}x'\\\ C_y\end{matrix}\right] &= \left[\begin{matrix}\cos\alpha&-\sin\alpha\\\sin\alpha&\cos\alpha\end{matrix}\right]\left[\begin{matrix}x\\\y\end{matrix}\right] \\\ \left[\begin{matrix}C_x\\\ y'\end{matrix}\right] &= \left[\begin{matrix}\cos\alpha&-\sin\alpha\\\sin\alpha&\cos\alpha\end{matrix}\right]\left[\begin{matrix}x\\\ -y\end{matrix}\right] \end{align*}
where $x'$ and $y'$ are just placeholders. Extracting appropriate rows from those formulae, we can transform that into one equation (notice the lack of minus sign in the matrix):
\begin{align*} \left[\begin{matrix}C_x\\\ C_y\end{matrix}\right] &= \left[\begin{matrix}\cos\alpha&\sin\alpha\\\sin\alpha&\cos\alpha\end{matrix}\right]\left[\begin{matrix}x\\\ y\end{matrix}\right] \end{align*}
with solution being:
\begin{align*} \left[\begin{matrix}\cos\alpha&\sin\alpha\\\sin\alpha&\cos\alpha\end{matrix}\right]^{-1} \left[\begin{matrix}C_x\\\ C_y\end{matrix}\right] &= \left[\begin{matrix}x\\\ y\end{matrix}\right] \\\ \sec{2\alpha}\left[\begin{matrix}\cos\alpha&-\sin\alpha\\\ -\sin\alpha&\cos\alpha\end{matrix}\right] \left[\begin{matrix}C_x\\\ C_y\end{matrix}\right] &= \left[\begin{matrix}x\\\ y\end{matrix}\right] \end{align*}
Please note, that this may not have a proper solution if $\alpha$ is to big!
Edit: Ok, I missed the comment about maximizing the area. Then again, consider this example:
The gray figure is a rhombus (it was created by rotating the black rectangle by $2\alpha$ ). To get the inscribed rectangle with the greatest area, consider the case when the rhombus would be a square--the greatest area would be when each rectangle vertex splits the rhombus edge in half (because then it is also a square and that is the rectangle with greatest area and given perimeter). But we can scale our rhombus (that may not be a square) so that is a square, obtain the solution there, and then scale back (the area will scale accordingly)! In conclusion the rectangle of greatest area will split the rhombus edges in half.
How to compute it? You could do it using the same approach:
\begin{align*} \left[\begin{matrix}x'\\\ C_y\end{matrix}\right] &= \left[\begin{matrix}\cos\alpha&-\sin\alpha\\\sin\alpha&\cos\alpha\end{matrix}\right]\left[\begin{matrix}x\\\y\end{matrix}\right] \\\ \left[\begin{matrix}x''\\\ -C_y\end{matrix}\right] &= \left[\begin{matrix}\cos(-\alpha)&-\sin(-\alpha)\\\sin(-\alpha)&\cos(-\alpha)\end{matrix}\right] \left[\begin{matrix}x\\\ -y\end{matrix}\right] \end{align*}
However, one can do it simpler: the vertex of the inscribed rectangle splits the gray edge in half, so $$2x\sin\alpha = C_y = 2y\cos\alpha\,.$$ This works if $C_x > C_y$, otherwise you need to do the same for $C_x$ instead. Moreover, even if $C_x > C_y$, you still need to check if the rotated rectangle fits into the boundary (because it may be that $C_x = C_y + \varepsilon $ ), if not, the solution from previous part will do.
Hope that helps ;-)