Kazun の競プロ記録

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

AtCoder Beginner Contest 246 A問題 Four Points

AtCoder ABC ABC246 A問題 100 pts

問題

提出解答

問題の概要

$xy$ 平面上に長方形がある. この長方形の各辺はどちらかの軸に平行であり, 面積は $0$ ではない. また, 長方形の4個の頂点のうち, 3個は $(x_1, y_1), (x_2, y_2), (x_3, y_3)$ であることがわかっている. 残りの1頂点を求めよ.

制約

$-100 \leq x_i, y_i \leq 100$
$(x_1, y_1), (x_2, y_2), (x_3, y_3)$ を頂点に持つ条件を満たす長方形が一意に存在する.

解法

このような長方形の4頂点は $a_1\neq a_2, b_1 \neq b_2$ なる4つの整数 $a_1, a_2, b_1, b_2$ を用いて, $(a_1, b_1), (a_1, b_2), (a_2, b_1), (a_2, b_2)$ と表せる.

ここで, 各座標について, $x$ 座標は $a_1, a_2$ が2回ずつ, $y$ 座標は $b_1, b_2$ が2回ずつ登場している. また, 存在するという制約も合わせて, $x_1, x_2, x_3$ にただ1回だけ現れる整数を $X$ , $y_1, y_2, y_3$ にただ1回だけ現れる整数を $Y$ としたとき, $(X,Y)$ が答えになる.