ABC292 F問題 Regular Triangle Inside a Rectangle

atcoder.jp

二分探索で求める方法もありますが、ここでは直接求めていきます。

xy平面上で (0,0), (A,0), (A,B), (0,B) を頂点とする長方形の内部に入る正三角形を考えていくことにします。
1辺の長さが L の正三角形の頂点の一つを原点(0,0) におくと、残りの2つの頂点の座標は (L \cos \theta, L \sin \theta), (L \cos (\theta + 60^\circ), L \sin (\theta + 60^\circ) )と表せます。
この正三角形が長方形の内部に入るための条件は、
0 \le L \cos \theta \le A
0 \le L \sin \theta \le B
0 \le L \cos (\theta + 60^\circ) \le A
0 \le L \sin (\theta + 60^\circ) \le B
です。 0 以上という条件から、 \theta の範囲は 0^\circ \le \theta \le 30^\circ と決まります。
この範囲では、
\cos (\theta + 60^\circ) \lt \cos \theta
\sin \theta \lt \sin (\theta + 60^\circ)
なので、
L \cos \theta \le A
L \sin (\theta + 60^\circ) \le B
つまり、
L \le \frac{A}{\cos \theta}
L \le \frac{B}{\sin (\theta + 60^\circ)}
が成り立てば長方形の内部です。

f(\theta) =\frac{A}{\cos \theta}, g(\theta) = \frac{B}{\sin (\theta + 60^\circ)} とおけば、 f(\theta) , g(\theta) の小さいほうが L の上限です。
\theta が大きくなると f(\theta) は大きくなる増加関数で、 g(\theta) は小さくなる減少関数です。
そのため、 \theta=\theta_0 (\gt0^\circ) で f(\theta_0) \gt g(\theta_0) であれば　 \theta を小さくすることで L の上限を増加させることが可能です。
逆に \theta=\theta_0 (\lt30^\circ) で f(\theta_0) \lt g(\theta_0) であれば　 \theta を大きくすることで L の上限を増加させることが可能です。

f(0^\circ) \gt g(0^\circ) となる条件、すなわち A \gt \frac{B}{ \frac{\sqrt{3}}{2}} のとき、 \theta はこれ以上小さくできないため、 g(0^\circ) = \frac{B}{ \frac{\sqrt{3}}{2}} が L の上限です。
f(30^\circ) \lt g(30^\circ) となる条件、すなわち \frac{A}{\frac{\sqrt{3}}{2} } \lt B のとき、 \theta はこれ以上大きくできないため、 f(30^\circ) = \frac{A}{\frac{\sqrt{3}}{2} } が L の上限です。
整理すると、
\sqrt{3} A \gt 2 B のとき L = \frac{2B}{ \sqrt{3}} が最大値
2 A \lt \sqrt{3} B のとき L = \frac{2A}{ \sqrt{3}} が最大値
になります。

この条件に当てはまらない場合は、 f(\theta_0) = g(\theta_0) になる \theta_0 で L が最大になります。
\frac{A}{\cos \theta_0} = \frac{B}{\sin (\theta_0 + 60^\circ)}
\frac{B}{A} = \frac{\sin (\theta_0 + 60^\circ)}{\cos \theta_0} = \frac{\sin \theta_0 \cos 60^\circ + \cos \theta_0 \sin 60^\circ}{\cos \theta_0} = \frac{1}{2}\tan \theta_0 + \frac{\sqrt{3}}{2}
\tan \theta_0 = \frac{2B}{A} - \sqrt{3}
この式から \theta_0 を求めて L=\frac{A}{\cos \theta_0} を計算すれば、これが最大値になります。

コード例 (Julia)

function solve()

  # 入力
  readInts() =  parse.(Int,split(readline()))
  readInt()  =  parse(Int,readline())

  A,B = readInts()

  s3 = sqrt(3.0)

  if s3 * A > 2B
    println(2B/s3)
    return
  end

  if 2A < s3 * B
    println(2A/s3)
    return
  end

  theta = atan(2B / A - s3)
  println(A/cos(theta))

end  # function solve

# main
solve()