Submission details
Task:Point in Polygon
Sender:aalto26jm_015
Submission time:2026-11-09 17:32:24 +0200
Language:C++ (C++20)
Status:READY
Result:ACCEPTED
Test results
testverdicttime
#1ACCEPTED0.01 sdetails
#2ACCEPTED0.01 sdetails
#3ACCEPTED0.00 sdetails
#4ACCEPTED0.00 sdetails
#5ACCEPTED0.00 sdetails
#6ACCEPTED0.00 sdetails
#7ACCEPTED0.00 sdetails
#8ACCEPTED0.00 sdetails
#9ACCEPTED0.00 sdetails
#10ACCEPTED0.00 sdetails
#11ACCEPTED0.00 sdetails
#12ACCEPTED0.00 sdetails
#13ACCEPTED0.00 sdetails
#14ACCEPTED0.00 sdetails

Code

#include <iostream>
#include <vector>
using namespace std;
typedef long long ll;

template<class T>
struct Point {
    T x, y;
    explicit Point(T x=0, T y=0) : x(x), y(y) {}
    bool operator<(Point p) const { return tie(x,y) < tie(p.x,p.y); }
    bool operator==(Point p) const { return tie(x,y)==tie(p.x,p.y); }
    Point operator+(Point p) const { return Point(x+p.x, y+p.y); }
    Point operator-(Point p) const { return Point(x-p.x, y-p.y); }
    Point operator*(T d) const { return Point(x*d, y*d); }
    Point operator/(T d) const { return Point(x/d, y/d); }
    T dot(Point p) const { return x*p.x + y*p.y; }
    T cross(Point p) const { return x*p.y - y*p.x; }
    T cross(Point a, Point b) const { return (a-*this).cross(b-*this); }
};

template<class Point> bool onSegment(Point s, Point e, Point p) {
    return p.cross(s, e) == 0 && (s - p).dot(e - p) <= 0;
}

template<class Point>
int inPolygon(vector<Point> &p, Point a, bool strict = true) {
    int cnt = 0, n = p.size();
    for (int i=0; i<n; i++) {
        Point q = p[(i + 1) % n];
        if (onSegment(p[i], q, a)) return 2;
        cnt ^= ((a.y<p[i].y) - (a.y<q.y)) * a.cross(p[i], q) > 0;
    }
    return cnt;
}

int main() {
    cin.tie(0)->sync_with_stdio(0);
    
    int n, m;
    cin >> n >> m;
    vector<Point<ll>> points(n);
    ll x, y;
    for (int i=0; i<n; i++) {
        cin >> x >> y;
        points[i] = Point<ll>(x, y);
    }

    for (int i=0; i<m; i++) {
        cin >> x >> y;
        Point<ll> testPoint(x, y);
        int res = inPolygon(points, testPoint);
        if (res == 2) {
            cout << "BOUNDARY\n";
        } else if (res == 0) {
            cout << "OUTSIDE\n";
        } else if (res == 1) {
            cout << "INSIDE\n";
        }
    }

    return 0;
}

Test details

Test 1

Verdict: ACCEPTED

input
100 1000
-7 -19
91 77
100 100
64 60
...

correct output
INSIDE
OUTSIDE
INSIDE
INSIDE
INSIDE
...

user output
INSIDE
OUTSIDE
INSIDE
INSIDE
INSIDE
...

Test 2

Verdict: ACCEPTED

input
1000 1000
365625896 -113418831
278762563 38777445
250367343 -96991975
175866909 -129766978
...

correct output
OUTSIDE
OUTSIDE
INSIDE
OUTSIDE
OUTSIDE
...

user output
OUTSIDE
OUTSIDE
INSIDE
OUTSIDE
OUTSIDE
...

Test 3

Verdict: ACCEPTED

input
4 1
1 5
5 5
5 1
1 1
...

correct output
INSIDE

user output
INSIDE

Test 4

Verdict: ACCEPTED

input
4 1
1 5
5 5
5 1
1 1
...

correct output
OUTSIDE

user output
OUTSIDE

Test 5

Verdict: ACCEPTED

input
4 1
1 100
2 50
1 20
0 50
...

correct output
INSIDE

user output
INSIDE

Test 6

Verdict: ACCEPTED

input
8 1
0 0
0 2
1 1
2 2
...

correct output
INSIDE

user output
INSIDE

Test 7

Verdict: ACCEPTED

input
4 4
0 0
3 0
3 4
0 4
...

correct output
INSIDE
BOUNDARY
OUTSIDE
BOUNDARY

user output
INSIDE
BOUNDARY
OUTSIDE
BOUNDARY

Test 8

Verdict: ACCEPTED

input
6 1
0 0
0 2
3 1
2 2
...

correct output
INSIDE

user output
INSIDE

Test 9

Verdict: ACCEPTED

input
3 1
0 0
1 1000000000
-3 0
1 1

correct output
OUTSIDE

user output
OUTSIDE

Test 10

Verdict: ACCEPTED

input
3 1
-100000 0
-1000000000 -999999999
1000000000 1000000000
0 0

correct output
OUTSIDE

user output
OUTSIDE

Test 11

Verdict: ACCEPTED

input
3 1
-100000 0
-999999999 -1000000000
1000 1000
0 0

correct output
INSIDE

user output
INSIDE

Test 12

Verdict: ACCEPTED

input
4 1
-4 1
-6 1
-6 -1
-4 -1
...

correct output
INSIDE

user output
INSIDE

Test 13

Verdict: ACCEPTED

input
3 1
0 10
0 -10
10 0
1 0

correct output
INSIDE

user output
INSIDE

Test 14

Verdict: ACCEPTED

input
3 1000
-536621709 -536621709
955833081 955833081
-1 1
-439278425 -439278425
...

correct output
BOUNDARY
BOUNDARY
BOUNDARY
BOUNDARY
BOUNDARY
...

user output
BOUNDARY
BOUNDARY
BOUNDARY
BOUNDARY
BOUNDARY
...