2012-02-04 Chain Code (UVa Live Archive North America 2010 - Rocky Mountain) UVa Live Archive Online Judge http://livearchive.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=408&page=show_problem&problem=2885 問題 図のようなチェインコードで境界が与えられるので内部の黒点の数を答えよ。 チェインコードの長さ<=100000 解法 チェインコードを舐めてゆき、左端の境界と右端の境界を記憶しておく。基本的には左右移動の開始時と上下移動をする時に境界を記憶する。ただし35等がきた場合は凸になってるので両側の境界を記憶し、06や27等ときた場合は凹んでいるのでスキップすること。境界が全て列挙し終わったら、後はソートして各区間を足せば答えになる。