Kazun の競プロ記録

競技プログラミングに関する様々な話題を執筆します.

AtCoder Beginner Contest 239 C問題 Knight Fork

AtCoder ABC ABC239 C問題 300 pts

問題

atcoder.jp

提出解答

(解法1) atcoder.jp

(解法2) atcoder.jp

問題の概要

次を満たす平面上の点 (X,Y) \in \mathbb{R}^2 は存在するか?

  • (X,Y) \in \mathbb{Z}^2. つまり, (X,Y) は格子点
  • \sqrt{(x_1-X)^2+(y_1-Y)^2}=\sqrt{(x_2-X)^2+(y_2-Y)^2}=\sqrt{5}

制約

  • -10^9 \leq x_1, y_1, x_2, y_2 \leq 10^9

解法1

整数 a,b に対する方程式 a^2+b^2=5 の解は

(a,b)=(\pm 1, \pm 2), \quad (\pm 2, \pm 1) \quad ({\text 複合任意})

の8個に限られる. よって, (x_1, y_1) との距離が \sqrt{5} である格子点は 8 個だけである. このような点それぞれについて (x_2, y_2) との距離が \sqrt{5} であるかどうかを見れば良い.

解法2

解法1から, \sqrt{(x_1-X)^2+(y_1-Y)^2} =5 ならば, |x_1-X|, |y_1-Y| \leq 2 である. つまり, 条件を満たす格子点は存在するならば, x_1-2 \leq X \leq x_1+2, y_1-2 \leq Y \leq y_2+2 の範囲に存在詞なければならないので, この範囲の中で (x_2, y_2) との距離が \sqrt{5} となる格子点が存在するかどうかを見れば良い.