Turtle Graphics (UVa Live Archive Asia - Site 4 (Korea) - 2007/2008 Seoul (Korea))

http://acmicpc-live-archive.uva.es/nuevoportal/data/problem.php?p=3908

問題

コンピュータのプログラムを使ってn個の線分で図形を書いていく。線分は方向dと長さfを使ってプログラムに入力する。このプログラムは線分が交差やオーバーラップすると、その交差の始まった場所から終わった場所までの軌跡を削除してしまう。最後に残った軌跡の線分の個数と長さを求めよ。
1<=n<=5000
d={N,S,E,W}
0<=f<=9(整数)

解法

訪れる整数座標の個数は高々50000点しかない。なので、いままで訪れた点とこれまでの軌跡を記録しておいて、すでに訪れた場所に来た場合は軌跡を逆順にたどり消去していけばよい。