読者です 読者をやめる 読者になる 読者になる

dohatsutsu’s diary

日記を書いています。

【No.021】「Live archive 7232 Path」

icpcarchive.ecs.baylor.edu

 

2015年、韓国のアジア地区予選

DaejoenのG問題です。

2015 ACM-ICPC Daejeon Regional

 

簡単な問題概要

ヒストグラムの形をした多角形があります。

どの辺もx軸かy軸に平行です。

左下の点をスタート地点とします。

多角形の辺上に、複数のゴール地点があります。

それぞれのゴール地点までの最短路を求めて、その総和を出力してください。

 

解法

すべてのゴール地点と多角形の頂点をイベント点として列挙します。

このとき、多角形の辺の上を右下の地点から時計回りにぐるっと一周するような順番に並べておきます。

 

あとは蟻本のp234のような凸包を行うだけです。

 

はじめに空のスタックを用意し、そこにイベント点を順番に追加していきます。

ただし、新しいイベント点をスタックに追加するたびに、凹んでいる部分を除去していく必要があります。

イメージ用スライド

www.slideshare.net

 

実際にACしたソースコード

github.com