AtCoder ARC 004 B - 2点間距離の最大と最小 ( Maximum and Minimum )
B - 2点間距離の最大と最小 ( Maximum and Minimum )
B: 2点間距離の最大と最小 ( Maximum and Minimum ) - AtCoder Regular Contest 004 | AtCoder
N + 1個(0 ~ N)点がx,y平面上にある時、i番目の点とi+1番目の点との距離が与えられる(0 <= i < N)。 この時、０番目の点とN番目の点の距離で取り得る最大の距離と最小の距離を出力する問題。
解法
最大距離
最大距離は与えられた各点の距離を全て足し合わせることで取得することができる。この時、与えられた点は全て一直線上に存在することになる。
最小距離
与えられた点の内０番目とN番目を除いた点で上手く直線を折ることで、０番目とN番目の距離を短くすることができる。 なので、どのように直線を折るかを考える。
与えられた点と点の距離の中で最も長い距離を見つけ、その線分の両サイドの点で直線を折り返す。これによって０番目とN番目の距離を最小にすることができる。
