ABC 183 | B - Billiards

問題

https://atcoder.jp/contests/abc183/tasks/abc183_b

考えたこと

$S_x = G_x$のときは真下に玉をぶつければいいので$S_x$が答えである。

次に$S_x != G_x$のときを考える。$G_x > S_x$のときは$G$と$S$を交換すればいいので$G_x < S_x$のみのときを考えればいい。

$G_x < S_x$のときは以下のようにx軸上の点と$S, G$のなす角$\theta$が同じになる。

上記のときの点を$mid$と置くと以下のようになる。

$mid$を$G_x$から$S_x$まで二分探索で求める事を考える。$\frac{S_y}{S_x-mid} < \frac{G_y}{mid - G_x}$ならばmidが目的の場所より左にある。そうでなければ右にある。このようにして誤差$10^{-6}$以下になるまで求めればいい。$100$回くらいで十分もとまる。もっと少なくても求まるが計算量に対した影響はないので$100$回としている。

コード

実装時のTips

• 出力で小数点12桁まで出すためにcout << fixed << std::setprecision(12)を利用している
• 結果が小数点のときもあるのでlong doubleを使っている

#include <bits/stdc++.h>

#include <atcoder/all>

using namespace std;
using namespace atcoder;
using ll = long long;
using ld = long double;
using uint = unsigned int;
using ull = unsigned long long;
const int MOD = 1e9 + 7;

int main() {
  cout << fixed << std::setprecision(12);
  ld sx, sy, gx, gy;
  cin >> sx >> sy >> gx >> gy;
  if (sx == gx) {
    cout << sx << endl;
    return 0;
  }

  if (sx < gx) {
    swap(sx, gx);
    swap(sy, gy);
  }

  ld left = gx;
  ld right = sx;
  ll cnt = 100;
  while (cnt) {
    ld mid = (left + right) / 2;
    ld a = sy / (sx - mid);
    ld b = gy / (mid - gx);
    if (a < b) {
      left = mid;
    } else {
      right = mid;
    }
    cnt--;
  }
  cout << left << endl;
  return 0;
}

別解

二分探索をしていたが以下のように等号で置き換え$mid$を直接求めればいいということに気づいた。

$$\frac{S_y}{S_x-mid} = \frac{G_y}{mid - G_x}$$

$$mid=\frac{S_xG_y + G_xS_y}{S_y + G_y}$$

よってコードは以下のようになる。

#include <bits/stdc++.h>

#include <atcoder/all>

using namespace std;
using namespace atcoder;
using ll = long long;
using ld = long double;
using uint = unsigned int;
using ull = unsigned long long;
const int MOD = 1e9 + 7;

int main() {
  cout << fixed << std::setprecision(12);
  ld sx, sy, gx, gy;
  cin >> sx >> sy >> gx >> gy;
  if (sx == gx) {
    cout << sx << endl;
    return 0;
  }

  if (sx < gx) {
    swap(sx, gx);
    swap(sy, gy);
  }

  ld ans = (sx * gy + gx * sy) / (sy + gy);
  cout << ans << endl;
  return 0;
}

参考

• https://zenn.dev/wapa5pow/articles/x-triangle-ec3a78ade93eddae354b