CodeChef September Challenge 2020 - Rotate the Polyline

• 問題
• AC

$v_i=P_iP_{i+1}$とした時、原点を通る直線$l$によってできた2つの（境界を含まない）半平面のそれぞれに連続した添え字のベクトルが並んでいれば、$l$に直交するベクトルが答えということになる。ただし、答えとなるベクトルは十分に原点に近い格子点を通る必要がある。

整数性の条件をいったん忘れると、直線$l$を表すベクトルの候補$u$は各$v_i$から偏角を左右に微小にずらした$2N$通りが考えられる。そこで偏角順の尺取り法をして、それぞれの$u$から偏角が$180 \degree$以内におさまるすべての$v_i$の添え字を保持することにする。添え字がすべて連続している瞬間があれば$u$を$90 \degree$回転したものを答えにすればよい。管理と判定はBITでできる。以下、実装のポイント:

• 尺取り法で区間を伸ばす場合の処理: ベクトルの候補$u$と$v_i$のクロス積がマイナスになるまで伸ばしていけばよい。^[1]
• 尺取り法で区間を縮める場合の処理: $u$と$v_i$のクロス積がプラスになるまで縮めればよい。
• $u$と同一か180度回転した偏角が$(v_i)$に含まれる場合、$u$（を$90\degree$回転したもの）は答えにできない。

さて、$2N$本の直線を用意する上で、整数性の条件を考慮しなくてはならない。単純化のために正数に限定して考える。ベクトル$(x, y)$から反時計回りに微小に偏角を進めたベクトルを得ることは、$y/x < 1$であればファレイ数列$F_{2\cdot 10^9}$において$y/x$の直後にある分数を得ることと同じである。$y/x \ge 1$の場合も、逆数を取って直前の分数を得ると考えればよい。やり方を知らないのでググったらstackexchangeの質問が見つかった。ファレイ数列の隣接項$p/q, c/d$は$cq-dp=1$を満たすので、$c, d$は互除法で求まるようだ。

---

1. クロス積がマイナスになるベクトルが存在しなかった場合はこれだとうまく処理できないように見える。こういうことが起こるのは、偏角ソートされた$(v_i)$の隣接項同士が$180\degree$より開いている場合だが、問題設定より全ベクトルを足すと$0$に戻るのでこの範囲に1つもベクトルがないということはありえない。 ↩︎