[ARC004B] 2点間距離の最大と最小 ( Maximum and Minimum )

间距最大值和最小值。( Maximum and Minimum ) 题目描述 平面上有n + 1个点，分别从0到n编号. 虽然不知道各点位置，但对于0以上且小于n的整数i，第i点和第i+1点的距离为d_i。 请求出从第0个点和第n个点的距离能够取到的值的最大值和最小值。 输入输出格式: 输入格式： 输入通过以下形式从标准输入中得到。 输入由n +1行构成. 对第1行赋予表示点编号的最大的整数n，( 1≤n≤500 ) . 在从第2行到第n +1行第i+2行( 0≤ i < n)中，表示第i号和第i+1号点的距离为整数d_i ( 1≤d_i≤30000) 输出格式： 输出被输出到标准输出，由2行构成. 在第1行中，输出作为第0点和第n点距离可取的最大值. 在第2行中，输出作为第0点和第n点距离可取的最小值. 误差为绝对误差或相对误差至少一方为10^(-3)以下允许 另外，最后输出换行。 感谢@Rising_Date 提供的翻译

[problemUrl]: https://atcoder.jp/contests/arc004/tasks/arc004_2 平面上に $ N+1 $ 個の点があり、それぞれ $ 0 $ から $ N $ までの番号が付けられています。 それぞれの点の位置はわかりませんが、$ 0 $ 以上 $ N $ 未満の整数 $ i $ について、$ i $ 番の点と $ i+1 $ 番の点の距離 $ d_i $ はわかっています。 $ 0 $ 番の点と $ N $ 番の点の距離としてとりうる値の最大と最小を求めてください。 入力は以下の形式で標準入力から与えられる。 > $ N $ $ d_{0} $ $ d_{1} $ : $ d_{N-1} $ - 入力は $ N+1 $ 行からなる。 - $ 1 $ 行目には点の番号の最大を表す整数 $ N(1≦N≦500) $ が与えられる。 - $ 2 $ 行目から $ N+1 $行目までの $ i+2 $ 行目 $ (0\ ≦\ i\ には、i $ 番と $ i+1 $ 番の点の距離を表す整数 $ d_i(1≦d_i≦30,000) $ が与えられる。 出力は標準出力に出力し、$ 2 $ 行からなる。 $ 1 $ 行目には、$ 0 $ 番の点と $ N $ 番の点の距離としてとりうる最大値を出力せよ。 $ 2 $ 行目には、$ 0 $ 番の点と $ N $ 番の点の距離としてとりうる最小値を出力せよ。 誤差は絶対誤差あるいは相対誤差の少なくとも片方が $ 10^{-3} $ 以下であれば許容する。 なお、最後には改行を出力せよ。 ``` <pre class="prettyprint linenums"> 1 1024 ``` ``` <pre class="prettyprint linenums"> 1024 1024 ``` - 入力より $ 0 $ 番の点と $ 1 $ 番の点があり、それらの間の距離は $ 1024 $ であることが分かります。 - 求める距離は、$ 0 $ 番の点と $ 1 $ 番の点の間の距離なので最大値も最小値もともに $ 1024 $ です。 ``` <pre class="prettyprint linenums"> 3 3 4 5 ``` ``` <pre class="prettyprint linenums"> 12 0 ``` - $ 0 $ 番の点と $ 3 $ 番の点の間の距離が最も大きくなるのは、下図(a)のように $ 0 $ 番の点と $ 3 $ 番の点を端にして $ 4 $ 点が一直線に並ぶ場合で、その距離は $ 3+4+5=12 $ となります。 - $ 0 $ 番の点と $ 3 $ 番の点の間の距離が最も小さくなるのは、下図(b)のように $ 0 $ 番の点と $ 3 $ 番の点の位置が等しい場合で、その距離は $ 0 $ となります。  ``` <pre class="prettyprint linenums"> 2 512 512 ``` ``` <pre class="prettyprint linenums"> 1024 0 ``` - $ 0 $ 番の点と $ 2 $ 番の点の間の距離が最も大きくなるのは、下図(a)のように $ 0 $ 番の点と $ 2 $ 番の点を端にして $ 3 $ 点が一直線に並ぶ場合で、その距離は $ 512+512=1024 $ となります。 - $ 0 $ 番の点と $ 2 $ 番の点の間の距離が最も小さくなるのは、下図(b)のように $ 0 $ 番の点と $ 2 $ 番の点の位置が等しい場合で、その距離は $ 0 $ となります。  ``` <pre class="prettyprint linenums"> 3 4 8 1 ``` ``` <pre class="prettyprint linenums"> 13 3 ``` - $ 0 $ 番の点と $ 3 $ 番の点の間の距離が最も大きくなるのは、下図(a)のように $ 0 $ 番の点と $ 3 $ 番の点を端にして $ 4 $ 点が一直線に並ぶ場合で、その距離は $ 4+8+1=13 $ となります。 - $ 0 $ 番の点と $ 3 $ 番の点は重なることができないので、$ 0 $ 番の点と $ 3 $ 番の点の間の距離が最も小さくなるのは下図(b)のように $ 1 $ 番の点と $ 2 $ 番の点を繋ぐ線分上に $ 0 $ 番の点と $ 3 $ 番の点がある場合で、その距離は $ 8-4-1=3 $ となります。  ``` <pre class="prettyprint linenums"> 10 1 2 3 4 5 6 7 8 9 10 ``` ``` <pre class="prettyprint linenums"> 55 0 ``` - $ 0 $ 番の点と $ 10 $ 番の点の間の距離が最も大きくなるのは、$ 0 $ 番の点から $ 10 $ 番の点が順に一直線に並ぶ場合で、その距離は $ 1+2+3+4+5+6+7+8+9+10=55 $ となります。 - $ 0 $ 番の点と $ 10 $ 番の点の間の距離が最も小さくなる一例は、$ 0 $ 番の点から $ 10 $ 番の点まで順に円型に並び、$ 0 $ 番の点と $ 10 $ 番の点の位置が等しくなった場合です。