入力が反時計回りに与えられるので、適切に rotate・split することで上側凸包と下側凸包に分離します。x 座標が最小のものが複数あるかどうかで上側と下側に重複する点の有無が変わることに注意してください（最大についても同様）。

クエリの点の x 座標が凸包の x 座標の範囲外の場合は自明に OUT です。そうでないとき、クエリ点が（該当の x 座標において）下側凸包より下にあるまたは上側凸包より上にある場合は OUT です。

そうでないとき、クエリ点の x 座標が凸包の x 座標の最小値または最大値と一致していたら ON です。そうでないとき、上側凸包または下側凸包の境界上にあれば ON です。それ以外のとき IN です。

上側凸包（下側も同様）との上下判定は、x 座標がクエリ点以下で最大の点・クエリ点以上で最小の点を二分探索で求め、それらがなす線分（あるいは点）との位置関係を調べればよいです。凸包の方の点の y 座標は整数になるとは限らないので、分母を払ったりしてうまくやりましょう。

提出 #40252904