長方形が \(2\) つのとき

「面積がそれぞれ \(S\) 以上、\(T\) 以上の \(2\) つの良い長方形を重ならないように配置することができるか？」という問題を考えます。

次の命題が真であることを示します。

• 条件を満たす配置に対し、 \(x\) 軸または \(y\) 軸に平行な直線 \(l\) であって、次の条件が成り立つようなものが存在する。
  • \(l\) はどの長方形の内部も通らない。
  • \(l\) によって \(xy\) 平面を \(2\) つに分けたとき、それぞれの領域に長方形が \(1\) つずつ配置されている。

一方の長方形を上図の灰色部で示します。 このとき、もう一方の長方形が \(2\) つ以上の赤い領域と重なることはありません（そうでなければ、灰色の長方形とも重なってしまいます）。よって、灰色の長方形の \(4\) 辺のいずれかを延長して得られる直線が前述の条件を満たします。

\(l\) を \(x\) 軸に平行であるようにとることができるならば、\(l\) は方程式 \(y = \left \lceil \frac{S}{X} \right \rceil\) で表されるとしてよいです。同様に、\(l\) を \(y\) 軸に平行であるようにとることができるならば、\(l\) は方程式 \(x = \left \lceil \frac{S}{Y} \right \rceil\) で表されるとしてよいです。これら \(2\) つの場合を調べることで答えを求めることができます。

長方形が \(3\) つのとき

長方形が \(2\) つの場合と同様に、次の命題を示します。

• 条件を満たす配置に対し、 \(x\) 軸または \(y\) 軸に平行な直線 \(l\) であって、次の条件が成り立つようなものが存在する。
  • \(l\) はどの長方形の内部も通らない。
  • \(l\) によって \(xy\) 平面を \(2\) つに分けたとき、一方の領域には長方形が \(1\) つ、もう一方の領域には \(2\) つ配置されている。

まず、適当な長方形を \(2\) つとり、それらに対して「長方形が \(2\) つのとき」で挙げた条件を満たす直線 \(l\) をとります。\(l\) は \(y\) 軸に平行であるとして一般性を失いません。

上図の点線のうち、残りの長方形の内部を通るものが高々一本であるときは、いずれかの点線が条件を満たします。両方の点線が残りの長方形の内部を通るとき、残りの長方形（下図の赤色部）の左右の青い領域はいずれの灰色の長方形とも重なりません。よって、赤い長方形の \(x\) 軸に平行な辺を延長して得られる直線のうちいずれかが条件を満たします。

以上から、

• \(l\) は \(x\) 軸、\(y\) 軸のどちらに平行か
• \(l\) によって \(xy\) 平面を \(2\) つの領域に分けたとき、長方形が \(1\) つのみ含まれる領域にはどの長方形が配置されているか

を全探索すればよいです。長方形が \(2\) つ含まれる領域については、「長方形が \(2\) つのとき」の問題を解くことで答えが求められます。

実装例