競技プログラミング日記

主に AtCoder の記事です

AtCoder Beginner Contest 292F

ABC292F

置き方が連続的で,これは全探索できないので, 最適な置き方やその性質を考える. すると,ある最適な置き方であって, 三角形の頂点の一つを,長方形の頂点と重ねたものが存在すると分かる.
以下,場合分けをしてそれぞれのmaxが答え. \(f_{\theta}\) の最大値は,binary search で最適な \(\theta\) を求める. 最適な \(\theta\) に対して, \(a / cos(\theta)\) が三角形の一辺.

使っている記号,マクロ等 "https://ecsmtlir.hatenablog.com/entry/2022/12/23/131925"

int main() {
  double a, b; cin >> a >> b;

  if(a > b) swap(a,b);
 
  const double pi = 3.1415926535;

  auto f = [&](double th) -> double {
    return a * cos(pi/6. - th) - b * cos(th);
  };
 
  double ans = -1e18;

  double t = 2*a/sqrt(3);
  if(b >= t){
    chmax(ans, t);
  }

  // 最適な c を求める
  double l = 0, r = pi/6.;
  while(abs(r-l)>1e-10){
    double c = (l+r)/2.;

    if(f(c) < 0) l = c;
    else r = c;
  }
  chmax(ans, a/cos(l));

  printf("%.10lf", ans);

  return 0;
}