ABC239 C - Knight Fork C++解答例

AtCoder Beginner Contest 239 - C Knight Fork を C++で解きます。

問題

問題文をAtCoder のページより引用します。

問題文

$xy$座標平面上の 2 つの格子点$(x_1, y_1), (x_2, y_2)$からの距離がともに$\sqrt{5}$である格子点は存在しますか？

制約

• $-10^{9} \leq x_1 \leq 10^{9}$
• $-10^{9} \leq y_1 \leq 10^{9}$
• $-10^{9} \leq x_2 \leq 10^{9}$
• $-10^{9} \leq y_2 \leq 10^{9}$
• $(x_1, y_1) \neq (x_2, y_2)$
• 入力はすべて整数である。

解答例

候補となる格子点を全探索する

問題文に示されている図より、ある点$(x, y)$からのユークリッド距離が$\sqrt{5}$になるような格子点は、$(x, y)$の周りの 8 点しかないことがわかります。
したがって、$(x_1, y_1)$からの距離が$\sqrt{5}$になる 8 点を全探索し、それぞれの点から$(x_2, y_2)$までの距離を計算し、距離が$\sqrt{5}$になる点があればYes、なければNoを出力すればよいです。

プログラム実装例

C++のプログラム実装例を以下に示します。
ある点の周りの点を列挙する際は、配列dx, dyを用意してループを回すとわかりやすいコードが書けます。
また、ユークリッド距離の計算の際にルートを取ることになりますが、浮動小数点の計算が入ると計算誤差を考慮しなければならなくなり面倒なので、2 乗のまま計算しています。

c.cpp

#include <iostream>
#include <vector>

int main() {
  int64_t x1, y1, x2, y2;
  std::cin >> x1 >> y1 >> x2 >> y2;

  std::vector<int64_t> dx = {2, 1, -1, -2, -2, -1, 1, 2};
  std::vector<int64_t> dy = {1, 2, 2, 1, -1, -2, -2, -1};

  bool ok = false;
  for (int64_t i = 0; i < 8; i++) {
    int64_t x = x1 + dx.at(i);
    int64_t y = y1 + dy.at(i);

    int64_t diff2 = (x2 - x) * (x2 - x) + (y2 - y) * (y2 - y);
    if (diff2 == 5) {
      ok = true;
    }
  }

  if (ok) {
    std::cout << "Yes" << std::endl;
  } else {
    std::cout << "No" << std::endl;
  }

  return 0;
}

実際に提出したコードはこちら。