【No.021】「Live archive 7232 Path」
2015年、韓国のアジア地区予選
DaejoenのG問題です。
2015 ACM-ICPC Daejeon Regional
簡単な問題概要
ヒストグラムの形をした多角形があります。
どの辺もx軸かy軸に平行です。
左下の点をスタート地点とします。
多角形の辺上に、複数のゴール地点があります。
それぞれのゴール地点までの最短路を求めて、その総和を出力してください。
解法
すべてのゴール地点と多角形の頂点をイベント点として列挙します。
このとき、多角形の辺の上を右下の地点から時計回りにぐるっと一周するような順番に並べておきます。
あとは蟻本のp234のような凸包を行うだけです。
はじめに空のスタックを用意し、そこにイベント点を順番に追加していきます。
ただし、新しいイベント点をスタックに追加するたびに、凹んでいる部分を除去していく必要があります。
イメージ用スライド
実際にACしたソースコード
