別解として、クエリごとに \(\mathrm{O}(\log N)\) で二分探索する解法を説明します。

便宜上、凸包の頂点を反時計回りに \(P_0, P_1, \dots, P_{N-1}\) と呼びます。また、クエリで与えられる頂点を \(p\) と呼びます。

\(P_0\) から \(P_1, P_2, \dots, P_{N-1}\) へ \(P_0\) を端点とする半直線を引くと、平面は \(N-1\) 個の領域に分割されます。 \(P_0 P_i\) と \(P_0 P_{i+1}\) の間の領域を \(S_i\) と呼ぶと、平面は \(S_1, S_2, \dots, S_{N-2}\) およびそれ以外の領域に分かれます。 (次の図は \(N=5\) の場合です。)

まず、\(p\) が \(S_1, S_2, \dots, S_{N-2}\) のどの領域(周上も含む)にも含まれないことは「半直線 \(P_0 P_1\) の進行方向右側にある」 OR 「半直線 \(P_0 P_{N-1}\) の進行方向左側にある」と同値です。よって外積を利用すれば判定できます。(外積を知らない人は、 公式解説 の説明が詳しいので合わせて読むことをお勧めします。)

\(p\) が \(S_1, S_2, \dots, S_{N-2}\) のいずれかの領域(周上も含む)に含まれる場合を考えます。
\(R(i)\) を \(P_1 P_0 P_i\) の角度 \((1 \leq i \leq N-1)\) とします。\(R(1), R(2), \dots, R(N-1)\) は \(0\) 度以上 \(180\) 度未満の範囲で単調増加しています。そして \(p\) が \(S_i\) に含まれる場合、\(P_1 P_0 p\) の角度は \(R(i)\) 以上 \(R(i+1)\) 以下です。よって、二分探索を利用すれば \(\mathrm{O}(\log N)\) で \(p\) がどの領域にあるかを求められます。
\(p\) の存在する領域が分かれば、(\(p\) が \(S_i\) に存在するとして) \(p\) が凸包の内部に存在する条件は「 \(P_i\) から \(P_{i+1}\) へ向かう直線の進行方向左側にある」と言えて、これは外積を利用して判定できます。

実装によっては \(p\) が周上に存在する場合がコーナーケースになるので注意が必要です。また、二分探索の部分について、角度を陽に計算すると浮動小数点数の誤差の影響で誤った答えを返す可能性があり正当性が不明なので、実装例では二分探索に外積を利用してこれを回避しています。

• 実装例(C++)

#include <iostream>
#include <utility>
#include <vector>
using namespace std;

using P = pair<long long, long long>;
P operator-(P a, P b) { return {a.first - b.first, a.second - b.second}; }
long long cross(P a, P b) { return a.first * b.second - a.second * b.first; }

int main() {
  int N, Q;
  cin >> N;
  vector<P> C(N);
  for (auto& c : C) cin >> c.first >> c.second;

  auto f = [&](P p) -> string {
    auto b1 = cross(C[1] - C[0], p - C[0]);
    auto b2 = cross(C[N - 1] - C[0], p - C[0]);
    if (b1 < 0 or b2 > 0) return "OUT";
    int L = 1, R = N - 1;
    while (L + 1 < R) {
      int M = (L + R) / 2;
      (cross(p - C[0], C[M] - C[0]) >= 0 ? R : L) = M;
    }
    auto v = cross(C[L] - p, C[R] - p);
    return v == 0 ? "ON" : v > 0 ? (b1 == 0 or b2 == 0 ? "ON" : "IN") : "OUT";
  };

  cin >> Q;
  while (Q--) {
    P p;
    cin >> p.first >> p.second;
    cout << f(p) << "\n";
  }
}