What is the optimal way of placing a square such that, the corners touch a set of points, and some set of points are outside the surface area?

Question

Consider a 2D square of $16 cm^2$ should be placed inside a bounded region of width=12cm and height=12cm. A square $s_i$ is positioned at the center $(x,y,\theta_z)$, has four corners $c_0^{s_i} \cdots c_3^{s_i}$. Now, the square should be positioned such that, it satisfy the following conditions:

(i) corners should touch $t_0 \cdots t_n \in T, T \in \mathbb{R}^{2}$

(ii) square surface area should not contain $e_0 \cdots e_n \in E, E\in \mathbb{R}^{2}$

Let us say, we want four squares $s_0 \cdots s_3 \in S$. My inefficient approach is below:

1. for a square $s$, sample $x,y$ from a $\mathcal{N}( \mu=0.0, \sigma=4.0)$, and $\theta_z$ from $\mathcal{N}( \mu=0.0, \sigma=3.14)$
2. check if $c_0^{s} \cdots c_3^s$ touches all the points in $T$
3. check if $c_0^{s} \cdots c_3^s$ excludes all the points in $E$
4. if (2) and (3) satisfied, insert the square $s_i \rightarrow S$ and continue till four valid squares are found.

Check the attached figure, which shows 10 squares. It is extremely time consuming, and I want to consider case of 100 squares. Is there any way this can be improved? Or can it be solved using some mathematical techniques or algorithms?

10 squares figure excluding 6 point, including 3 points