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

[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} $ 以下であれば許容する。 なお、最後には改行を出力せよ。 ```

1
1024
```

 ```
1024
1024
```

- 入力より $ 0 $ 番の点と $ 1 $ 番の点があり、それらの間の距離は $ 1024 $ であることが分かります。
- 求める距離は、$ 0 $ 番の点と $ 1 $ 番の点の間の距離なので最大値も最小値もともに $ 1024 $ です。
 
```
3
3
4
5
```

 ```
12
0
```

- $ 0 $ 番の点と $ 3 $ 番の点の間の距離が最も大きくなるのは、下図(a)のように $ 0 $ 番の点と $ 3 $ 番の点を端にして $ 4 $ 点が一直線に並ぶ場合で、その距離は $ 3+4+5=12 $ となります。
- $ 0 $ 番の点と $ 3 $ 番の点の間の距離が最も小さくなるのは、下図(b)のように $ 0 $ 番の点と $ 3 $ 番の点の位置が等しい場合で、その距離は $ 0 $ となります。

![](https://cdn.luogu.com.cn/upload/vjudge_pic/AT_arc004_2/ba2a862971bf0c12b687c04aa18b7c0205f09bc3.png)

 ```
2
512
512
```

 ```
1024
0
```

- $ 0 $ 番の点と $ 2 $ 番の点の間の距離が最も大きくなるのは、下図(a)のように $ 0 $ 番の点と $ 2 $ 番の点を端にして $ 3 $ 点が一直線に並ぶ場合で、その距離は $ 512+512=1024 $ となります。
- $ 0 $ 番の点と $ 2 $ 番の点の間の距離が最も小さくなるのは、下図(b)のように $ 0 $ 番の点と $ 2 $ 番の点の位置が等しい場合で、その距離は $ 0 $ となります。

![](https://cdn.luogu.com.cn/upload/vjudge_pic/AT_arc004_2/294c83efd0ca5b33020d5d87feae968886557560.png)

 ```
3
4
8
1
```

 ```
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 $ となります。

![](https://cdn.luogu.com.cn/upload/vjudge_pic/AT_arc004_2/24f5e99a8a04c60da45588044b06345547a6d88b.png)

 ```
10
1
2
3
4
5
6
7
8
9
10
```

 ```
55
0
```

- $ 0 $ 番の点と $ 10 $ 番の点の間の距離が最も大きくなるのは、$ 0 $ 番の点から $ 10 $ 番の点が順に一直線に並ぶ場合で、その距離は $ 1+2+3+4+5+6+7+8+9+10=55 $ となります。
- $ 0 $ 番の点と $ 10 $ 番の点の間の距離が最も小さくなる一例は、$ 0 $ 番の点から $ 10 $ 番の点まで順に円型に並び、$ 0 $ 番の点と $ 10 $ 番の点の位置が等しくなった場合です。
                            

N/A

N/A