AtCoder Regular Contest 004 B - 2点間距離の最大と最小 ( Maximum and Minimum )

問題概要

　2次元平面上の個の点について、番目と番目の点の間の距離が分かっている。この時の番目の点と番目の点の距離について考え得るmaxとminを求めよ。

atcoder.jp

解法

　まず、maxは明らかに。

　様々なところで言及されているが、入力をソートしても一般性を失わない場合、とりあえずソートしてみると良かったり悪かったりするので降順ソートする。

　すると、例えば番目の点が移動可能な範囲は番目の点を中心とした、半径の円周上である。

　これを拡張して考えるとminは、
\begin{eqnarray}
\left\{
\begin{array}{l}
0(d_0≦\displaystyle \sum_{i=1}^{N-1} d_i) \\
d_0-\displaystyle \sum_{i=1}^{N-1} d_i(otherwise)
\end{array}
\right.
\end{eqnarray}

となる。これを実装して、AC。。

atcoder.jp