X Clash

境界に沿った順に頂点 $P_1, P_2, \cdots, P_N$ を持つ単純多角形 $G$ が与えられる。$G$ は内部と境界を含む。

$P_1$ と $P_2$ を通る直線を $\ell$ とする。多角形全体は $\ell$ の片側にある。その側の閉半平面を とし、壁が占める領域を とする。

最初、$G$ は壁の空洞にぴったり収まっている。$G$ を回転させずに連続的に平行移動し、$G$ のすべての点を $H$ の外に出せるか判定せよ。

移動中、多角形と壁が重なる部分の面積は常に $0$ でなければならない。境界同士の接触や、境界に沿って滑る移動は許される。途中で移動方向を変えてもよい。壁と $H$ は動かない。

入力は次の形式で与えられる。

$N$ $x_1\ y_1$ $x_2\ y_2$

多角形を完全に取り出せるなら YES を、そうでなければ NO を出力せよ。

• $3 \leq N \leq 1000$.
• $-10\,000 \leq x_i,y_i \leq 10\,000$ ().