新規
編集
添付
時間制限:1000ミリ秒
メモリ制限:10000KB
壁
問題 
昔あるとき、貪欲な王がいて、建築士に城を囲む壁の建設を命じた。王はとても貪欲なので、完璧な形と高い塔をもつ美しいレンガの壁を作るという建築士の提案を聞かなかった。そのかわり彼は、できるだけ少ない量の石と労働で、かつ壁が城に一定距離以上近づくことのないように壁を建設することを命じた。もし建築士がこの要求を満たす最低限よりも多い資源を使ったことが王に発見されると、建築士の首は飛んでしまう。そのうえ、王は建築士に、壁を建設するのに必要な最低限の資源量を示すプランを早急に示すことを要求した。
あなたの仕事は、かわいそうな建築士の首がはねられないようにするため、王の要求を満たすような壁のうち最短なものの長さを求めるプログラムを書くことである。
実はこの仕事はいくらか単純化されていて、王の城は多角形の形状をしていて、平坦な地面に建設されている。さらに、建築士はすでに、直交座標に基づいて城の全ての頂点の座標をフィート単位で精密に計測している。
入力
入力の最初の行は2つの整数NとLが空白を区切りとして書かれている。N(3 <= N <= 1000)は王の城の頂点数であり、L(1 <= L <= 1000)は壁と城との距離として王が許したフィート単位の長さである。
続くN行は城の頂点が時計回りに記述されている。各行は2つの整数Xi,Yi(-10000 <= Xi, Yi <= 10000)が空白を区切りとして書かれていて、i番目の頂点の座標をあらわす。全ての頂点の座標は互いに異なり、辺同士は頂点を除いてどこでも交差しない。
出力
王の要求を満足させて建設可能な壁のなかで最も短いものの長さをあらわす1行を出力せよ。小数はまだ発明されていないので、フィート単位の整数で表現しなければならない。しかし、王はあまり大きな誤差は許容できないので、誤差が8インチ(1フィート=12インチ)以内であるように丸める必要がある。
入力例
9 100 200 400 300 400 300 300 400 300 400 400 500 400 500 200 350 200 200 200
出力例
1628
ヒント
結果は四捨五入で問題ない。
出典
Northeastern Europe 2001
