2684: Polygonal Line Search

ICPC PKU AC

http://acm.pku.edu.cn/JudgeOnline/problem?id=2684
久々にやった。今年は頑張って東大勢とさいたま+その他大勢の猛者に勝つ！今年はほぼ確実にawakiaと出れる最後のICPCなので気合い入ってます。もう一人の新チームメイトもポテンシャルがやばいので気合いマシマシ。俺自身も留学することになったら来年は出られないので、その点でも必死(仮に東大に入れたら誰か俺を受け入れてくださいｗ)。

で、解いてみた。同じ形をした図形を探す問題。制約が多く、

  • 図形は線で構成される
  • 線はX,Yのどちらかの軸に平行である
  • 回転、平行移動した図形のみ同じ形と見なす(拡大縮小は含まれない)
  • 線は左右どちらかに90度曲がる事しかできない

という感じ。これを使うとうまく解ける。まずは線分を

移動距離, 曲がった方向, 移動距離, 曲がった方向, ..., 移動距離

と言うデータに変換する。こうすることで平行移動と回転を無視して図形を比較することができる。一つ注意すべき事として、図形には端点が2つあるので、2通りのデータができあがると言うこと。もう片方の端点から辿ったデータは、元のデータをreverseしてから、曲がった方向を反転させてやれば良い。あとは残りの図形のデータを入力し、その二つと比較して終了。

久しぶりだったので頭がなまってた。来週から本格的にリハビリ開始。