Submission #41141099

---

Source Code Expand

#include <atcoder/all>
using namespace atcoder;
#include <bits/stdc++.h>
#include <cassert>
using namespace std;
using ll = long long;
const double pi = 3.14159265359;
const ll INF = 1LL << 60;

template<class T> inline bool chmin(T& a, T b){ if (a > b){a = b; return true;} return false;}
template<class T> inline bool chmax(T& a, T b){ if (a < b){a = b; return true;} return false;}

//using mint = modint998244353;
//using mint = modint1000000007;
//using mint = modint;  // mint::set_mod(p); later
//using mint = static_modint<1000000009>;

int N;
vector<ll> x, y;

// (a, b) がベクトル Pi->Pj のどちらにあるかを調べるために外積を求める
ll check(int i, int j, ll u, ll v)
{
  ll a = x[j] - x[i];
  ll b = y[j] - y[i];
  ll c = u - x[i];
  ll d = v - y[i];
  return a*d - b*c;
}

void solve(ll u, ll v)
{
  if (check(0, 1, u, v) < 0 || check(0, N-1, u, v) > 0){
    cout << "OUT\n";
    return;
  }

  // P0->P1 上
  if (check(0, 1, u, v) == 0){
    ll a = x[1] - x[0];
    ll b = y[1] - y[0];
    ll c = u - x[0];
    ll d = v - y[0];
    if (a*a + b*b >= c*c + d*d){
      cout << "ON\n";
    } else {
      cout << "OUT\n";
    }
    return;
  }

  // P0->PN-1上
  if (check(0, N-1, u, v) == 0){
    ll a = x[N-1] - x[0];
    ll b = y[N-1] - y[0];
    ll c = u - x[0];
    ll d = v - y[0];
    if (a*a + b*b >= c*c + d*d){
      cout << "ON\n";
    } else {
      cout << "OUT\n";
    }
    return;
  }
  
  // どの三角形の間に入り得るのかをニブタン
  int ok = 1;
  int ng = N-1;
  while (abs(ok-ng) > 1){
    int mid = (ok + ng) / 2;
    if (check(0, mid, u, v) >= 0){
      ok = mid;
    } else {
      ng = mid;
    }
  }

  // 実際に三角形の中に入っているか
  ll op = check(ok, ok+1, u, v); // outer product
  if (op == 0){
    cout << "ON\n";
  } else if (op > 0){
    cout << "IN\n";
  } else {
    cout << "OUT\n";
  }
}

int main()
{
  cin.tie(0); cout.tie(0); ios::sync_with_stdio(false);

  // 入力
  cin >> N;
  x.resize(N);
  y.resize(N);
  for (int i = 0; i < N; i++) cin >> x[i] >> y[i];

  int Q;
  cin >> Q;
  for (int i = 0; i < Q; i++){
    ll a, b;
    cin >> a >> b;
    solve(a, b);
  }
  
  return 0;
}

Submission Info

Judge Result