徒然

思いついたら書きます

AtCoder Beginner Contest 292 F - Regular Triangle Inside a Rectangle 解説

競技プログラミング

はじめに

ABC292のF問題で幾何問題が出ました。
自分は他の方と解答アプローチが異なったので解説記事を書いてみます。

問題

縦 $A$ 、横 $B$ の長方形で囲まれた内部に描ける正三角形の一辺の長さの最大値を求めよ。

解答

前提として $A \le B$ とします。 $A \gt B$ の場合はswapして考えます。
また $B \ge \frac{2}{\sqrt 3}A$ のときは $\frac{2}{\sqrt 3}A$ が答えになるので説明を省きます。*1

与えられた四角形を $EFGH$ として、点 $E$ 及び辺 $FG$ に接する正三角形 $EPQ$ を描きます。
各辺の長さは $x$ とします。
そして点 $Q$ から辺 $EH$ に垂線を引き、交点を $T$ とします。

すると $\angle FEP$ は $\arccos \frac{A}{x}$ で表され、 $\angle HEQ$ は $\frac{\pi}{6} - \arccos \frac{A}{x}$ となります。
したがって $ET$ の長さは $x \cos (\frac{\pi}{6} - \arccos \frac{A}{x})$ となり、 $B$ 以下であれば長方形の内部である条件を満たし、 $B$ と一致するときが最大となります。

このような $x$ は二分探索で求めることができます。探索範囲は条件より $A \le x \lt \frac{2}{\sqrt 3}A$ です。*2

実装

所感

がっつり数学問題なので苦手な人には辛そうですが、アプローチ方法が複数あって個人的には良い問題だなと思いました。

*1:正三角形の1辺が長さ $B$ の辺に接するのが最適となる

*2:出力例1を参考に、下限を $(\sqrt 6 - \sqrt 2)A$ としても良いです。