http://arc076.contest.atcoder.jp/tasks/arc076_c
解法
http://arc076.contest.atcoder.jp/submissions/1380534
まず大切なことが「同じ整数が書かれている座標の両方が長方形の境界線上に無いものは考えなくて良い」ということ。
あとは、任意の2つの同じ数字が書かれている座標同士を結んだときに交わらないならば、YES"。交わるものがあるなら"NO"
交差するかの判定はstackを使って判定する。
まず、長方形の境界線上での座標を1次元に変換する(parse関数)。
ルールとしては
- 上の辺上にあるとき(y == 0)
- 右の辺上にあるとき(x == R)
- 下の辺上にあるとき(y == C)
- 左の辺上にあるとき(otherwise)
で分けて、1次元に変換したときの座標に変換する
交差判定では、1次元に変換した座標を昇順にして先頭から順に判定していく。
stackを用いる。
ダメなパターンというのは任意の数の間に閉じていない数が存在している場合である。
これはstackに小さい座標から順に番号を入れていくが、先頭が同じ番号であれば互いに除去し、それ以外は普通にいれるようにしていき、最終的にスタックが空であれば、交差しない。そうでないなら、交差すると判定する。
