まず頂点が反時計回りに与えられる場合を考える。 上に完全に含まれる辺を除き、各有向辺 に対して、衝突しない微小な平行移動ベクトル は を満たす必要がある。負ならその辺の近くで壁と正の面積だけ重なる。等号は境界に沿う移動なので許される。 上の辺にはこの条件を課さない。
これらの条件を満たす外向きの があれば、その方向に移動し続ければよい。 に平行な直線で多角形を切ると、壁の内部にある境界では 方向に多角形の内部から外部へ出られない。したがって空でない内部断面は開口まで続く区間となり、外向きに移しても壁に入らない。頂点を通る断面は極限で扱える。
逆に、連続な経路で取り出せるなら、その経路上の十分小さい非零の変位もすべての条件を満たす。開口上の辺は同じ向きを持ち、全辺のベクトルの和は なので、可能な非零の変位は外向きとなる。開口に平行なら全辺に平行でなければならず、面積が正であることに反する。途中で方向を変える必要はない。
可能な方向の区間の境界は、いずれかの辺に平行である。各辺の両方向を候補としてすべての条件を調べれば で解ける。添付の naive はこの方法であり、全体の制約でも間に合う。
線形時間の解法もある。 とし、反時計回りなら 、時計回りなら とする。 と定める。正の倍率を無視すると外向きのベクトルは と書ける。各辺の条件は
となる。係数が正なら下限、負なら上限を更新する。係数が で右辺が正なら不可能である。最後の下限が上限以下なら可能であり、等号も許す。
分数を分子と正の分母で保持し、交差積で比較すれば浮動小数点数は不要である。時間計算量は 、入力の保存領域は である。内積と外積の絶対値は 以下、分数比較の各積の絶対値は 以下なので、符号付き ビット整数で足りる。
サブタスク 1 は三角形のみである。開口と反対側の頂点を開口の内部の点へ向かって移動すればよく、常に取り出せる。入力の読み込みを含めて 時間である。
Solution written by GPT
