Official

F - Regular Triangle Inside a Rectangle Editorial by m_99


最適な正三角形の描き方において、正三角形と長方形は頂点を 少なくとも \(1\) 個共有するものとして良いです。

証明 正三角形上の点であって最も上・下・右・左にあるようなものを考えると、それぞれ正三角形の頂点を少なくとも \(1\) 個含みます。また、ある頂点が最も上かつ下になること、および最も右かつ左になることはないため、正三角形に対して以下のうちどれかが言えます。

  • 頂点であって、正三角形上で最も上かつ最も右にあるようなものが存在する
  • 頂点であって、正三角形上で最も上かつ最も左にあるようなものが存在する
  • 頂点であって、正三角形上で最も下かつ最も右にあるようなものが存在する
  • 頂点であって、正三角形上で最も下かつ最も左にあるようなものが存在する

たとえば \(1\) 番目のことがいえる場合、その頂点が長方形の右上と一致するように正三角形を平行移動させることで正三角形と長方形が頂点を少なくとも \(1\) 個共有するように出来るため、最適な正三角形の描き方においてもこのように仮定出来ます。

正三角形の一辺の長さが \(l\) の時に長方形内部に描けるかの判定を考えます。(本問の解法を先に書くと、判定が出来た場合、これを利用して長方形内部に描ける正三角形の一辺の長さ \(l\) の最大値を二分探索すれば良いです)

適当に回転や反転をし、長方形の左下の頂点が正三角形の頂点と一致するものとします。長方形の下側の辺と正三角形の下側の辺のなす角を \(\theta\) とすると、長方形の下側の辺と正三角形の上側の辺のなす角は \(\theta + 60^\circ\) となります。また、\(\theta \geq 0^\circ, \theta + 60^\circ \leq 90 ^ \circ\) より \(0^\circ \leq \theta \leq 30^\circ\) です。 ここで、正三角形の横幅は \(l \cos \theta\)、縦幅は \(l \sin \theta\) となるため、\(\cos \theta \leq \frac{B}{l}, \sin\theta \leq \frac{A}{l}, 0^\circ \leq \theta \leq 30^\circ\) を満たす \(\theta\) が存在するかどうかを考えることになります。
( \(0^\circ \leq \theta \leq 30^\circ\) の範囲内で) \(\cos \theta\)\(\theta\) の増加に伴って減少し、\(\sin\theta\)\(\theta\) の増加に伴って増加します。このことから、\(\cos \theta \leq \frac{B}{l}\) を満たす最小の \(\theta\) を値域内で求め(二分探索を使うか、\(\frac{B}{l}\)\(0\) 以上 \(\frac{\sqrt{3}}{2}\) 以下であるかどうかで場合分けをしながら \(\cos^{-1} \theta\) を使うことで可能です), これが \(\sin \theta \leq \frac{A}{l}\) を満たすかどうかを確認すれば良いです。

posted:
last update: