Chain Code (UVa Live Archive North America 2010 - Rocky Mountain)

http://livearchive.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=408&page=show_problem&problem=2885

問題

図のようなチェインコードで境界が与えられるので内部の黒点の数を答えよ。
チェインコードの長さ<=100000

解法

チェインコードを舐めてゆき、左端の境界と右端の境界を記憶しておく。基本的には左右移動の開始時と上下移動をする時に境界を記憶する。ただし35等がきた場合は凸になってるので両側の境界を記憶し、06や27等ときた場合は凹んでいるのでスキップすること。境界が全て列挙し終わったら、後はソートして各区間を足せば答えになる。