CSES Point In Polygon
// compile: make data
// run: time ./data < big.in > big.out
#include <bits/stdc++.h>
using namespace std;
#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")
#ifdef LOCAL
#include <debug/codeforces.h>
#define debug(x...) _debug_print(#x, x);
#define Debug(x...) _debug_print_format(#x, x);
std::ifstream terminal("/dev/tty");
#define PP cerr<<"\033[1;30mpause...\e[0m",terminal.ignore();
#else
#define debug(x...)
#define Debug(x...)
#define PP
#endif
template<typename...Args> void print_(Args...args){((cout<<args<<" "),...)<<endl;}
#define rep(i,a,b) for(int i=(a);i<(int)(b);++i)
#define sz(v) ((int)(v).size())
#define print(...) print_(__VA_ARGS__);
#define FIND(a, x) ((find(a.begin(),a.end(),(x))!=a.end())?1:0)
#define cmin(x,...) x=min({(x),__VA_ARGS__})
#define cmax(x,...) x=max({(x),__VA_ARGS__})
#define INTMAX (int)(9223372036854775807)
#define INF (int)(1152921504606846976)
#define NaN (int)(0x8b88e1d0595d51d1)
#define double long double
#define int long long
#define uint unsigned long long
#define MAXN 200010

template <typename T> struct point2d {
    T x, y;
    point2d() {}
    point2d(int X, int Y): x(X), y(Y) {}
    point2d<T> operator+(const point2d<T> &rhs) const {
        point2d<T> res(x + rhs.x, y + rhs.y);
        return res;
    }
    point2d<T> operator-(const point2d<T> &rhs) const {
        point2d<T> res(x - rhs.x, y - rhs.y);
        return res;
    }
    bool operator==(const point2d<T> &rhs) const {
        return x == rhs.x && y == rhs.y;
    }
    T dot(const point2d<T> &rhs) const {
        return x * rhs.x + y * rhs.y;
    }
    T cross2(const point2d<T> &rhs) const {
        return x * rhs.y - y * rhs.x;
    }
    double norm() const {
        return sqrt(x * x + y * y);
    }
};

template <typename T> struct line2d {
    point2d<T> a, b;
    line2d() {}
    line2d(point2d<T> A, point2d<T> B): a(A), b(B) {}
    bool on(point2d<T> p, bool ica = 1, bool icb = 1) {
        if (!ica && a == p) return false;
        if (!icb && b == p) return false;
        point2d<T> v1 = p - a, v2 = p - b;
        return v1.cross2(v2) == 0 && v1.dot(v2) <= 0;
    }
    bool intersect(line2d<T> &rhs, bool ica = 1, bool icb = 1) {
        line2d<T> &lhs = *this;
        if (!ica && rhs.on(lhs.a)) return false;
        if (!icb && rhs.on(lhs.b)) return false;
        if (lhs.on(rhs.a, ica, icb) || lhs.on(rhs.b, ica, icb)) return true;
        if ((ica && rhs.on(lhs.a)) || (icb && rhs.on(lhs.b))) return true;
        auto mul = [](T A, T B) -> T {
            if (A == 0 || B == 0) return 0;
            if ((A > 0 && B > 0) || (A < 0 && B < 0)) return 1;
            return -1;
        };
        point2d<T> ab = lhs.b - lhs.a;
        point2d<T> ac = rhs.a - lhs.a;
        point2d<T> ad = rhs.b - lhs.a;
        point2d<T> cd = rhs.b - rhs.a;
        point2d<T> ca = lhs.a - rhs.a;
        point2d<T> cb = lhs.b - rhs.a;
        if (mul(ab.cross2(ac), ab.cross2(ad)) < 0 && mul(cd.cross2(ca), cd.cross2(cb)) < 0) return true;
        return false;
    }
};

template <typename T> struct polygon2d {
    vector<point2d<T>> p;
    polygon2d() {}
    polygon2d(vector<point2d<T>> a): p(a) {}
    void add(const point2d<T> q) {p.push_back(q); }
    T area() const {
        T res = 0;
        rep(i, 0, p.size()) {
            int j = (i + 1) % p.size();
            res += p[i].cross2(p[j]);
        }
        return abs(res);
    }
    int in(const point2d<T> &q) const {
        line2d l(q, point2d<T>((T)(1e9+7), q.y));
        int cnt = 0;
        rep(i, 0, sz(p)) {
            point2d<T> a = p[i], b = p[(i+1) % sz(p)];
            line2d m(a, b);
            if (m.on(q)) return 0;
            if (!m.intersect(l)) continue;
            int maxy = max(a.y, b.y);
            if (maxy > q.y) ++cnt;
        }
        return cnt&1 ? 1 : -1;
    }
};

int32_t main() {
    ios::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr);

    int n, m; cin >> n >> m;
    polygon2d<int> p;
    rep(i, 0, n) {
        int x, y; cin >> x >> y;
        p.add(point2d<int>(x, y));
    }
    rep(i, 0, m) {
        int x, y; cin >> x >> y;
        int res = p.in(point2d<int>(x, y)); 
        if (res == 1) printf("INSIDE\n");
        else if (res == -1) printf("OUTSIDE\n");
        else printf("BOUNDARY\n");
    }

    return 0;
}

Comments

  1. 2 months ago
    2025-12-06 2:31:40

    Okay, winchidoapp… a mobile app? Perfect for gaming on the go! Hope the interface is smooth and the game selection is top-notch. Downloading winchidoapp now to give it a spin!

  2. 2 months ago
    2025-12-19 13:46:41

    Heard about F8betceo. The name’s a bit much, TBH, but the platform is functional. Got some sportsbook options, and some casino games too. Pretty standard stuff, but hey, it works. Try it out if you are curious: f8betceo

  3. 1 month ago
    2025-12-29 6:15:00

    Yo, just checked out vvjlorg! Not gonna lie, things seem pretty solid. Layout’s clean, and it’s easy to navigate. Seems like a decent spot if you’re looking for something new. Check it out for yourself: vvjlorg

  4. 1 week ago
    2026-1-24 23:43:17

    Phdream33, I’ve heard whispers. Tempted to see what all the hype is about. Maybe I’ll get lucky! Discover it here: phdream33

  5. 1 week ago
    2026-1-24 23:43:33

    Mariobettwitter… Betting AND Twitter? This I gotta see. Wonder what kind of action they’ve got. Check it atmariobettwitter

  6. 1 week ago
    2026-1-24 23:43:48

    77winapk – time to download my luck and see if it works out for me. Hoping I get the big jackpot! Try it out now! 77winapk

Send Comment Edit Comment


				
|´・ω・)ノ
ヾ(≧∇≦*)ゝ
(☆ω☆)
(╯‵□′)╯︵┴─┴
 ̄﹃ ̄
(/ω\)
∠( ᐛ 」∠)_
(๑•̀ㅁ•́ฅ)
→_→
୧(๑•̀⌄•́๑)૭
٩(ˊᗜˋ*)و
(ノ°ο°)ノ
(´இ皿இ`)
⌇●﹏●⌇
(ฅ´ω`ฅ)
(╯°A°)╯︵○○○
φ( ̄∇ ̄o)
ヾ(´・ ・`。)ノ"
( ง ᵒ̌皿ᵒ̌)ง⁼³₌₃
(ó﹏ò。)
Σ(っ °Д °;)っ
( ,,´・ω・)ノ"(´っω・`。)
╮(╯▽╰)╭
o(*////▽////*)q
>﹏<
( ๑´•ω•) "(ㆆᴗㆆ)
😂
😀
😅
😊
🙂
🙃
😌
😍
😘
😜
😝
😏
😒
🙄
😳
😡
😔
😫
😱
😭
💩
👻
🙌
🖕
👍
👫
👬
👭
🌚
🌝
🙈
💊
😶
🙏
🍦
🍉
😣
Source: github.com/k4yt3x/flowerhd
颜文字
Emoji
小恐龙
花!
Previous
Next