Kazun の競プロ記録

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

AtCoder Beginner Contest 234 B 問題 Longest Segment

AtCoder ABC ABC234 B問題 200 pts

問題

提出解答

問題の概要

座標平面上に相異なる $N$ 点があり, $i$ 番目の点の座標は $(x_i, y_i)$ である.

この $N$ 点から $2$ 点を選ぶとき, その $2$ 点を端点とする線分の長さの最大値を求めよ.

制約

$2 \leq N \leq 100$
$-1000 \leq x_i, y_i \leq 1000$
$i \neq j \Rightarrow (x_i,y_i) \neq (x_j,y_j)$

解法

2点を選ぶ方法は $\frac{N(N-1)}{2}$ 通りで, $N=100$ としても $4950$ 通りと非常に小さい. よって, 全部の組み合わせについてを見て, その最大値を答えれば良い.

ちなみに, $2$ 点 $(x,y),(x',y')$ を端点とする線分の長さは $\sqrt{(x-x')^2+(y-y')^2}$ である.