CSES - Aalto Competitive Programming 2024 - wk10 - Mon - Results
Submission details
Task:Point in Polygon
Sender:minghao
Submission time:2024-11-11 16:58:03 +0200
Language:C++ (C++20)
Status:READY
Result:
Test results
testverdicttime
#10.01 sdetails
#2ACCEPTED0.02 sdetails
#3ACCEPTED0.00 sdetails
#4ACCEPTED0.00 sdetails
#5ACCEPTED0.00 sdetails
#60.00 sdetails
#7ACCEPTED0.00 sdetails
#8ACCEPTED0.00 sdetails
#9ACCEPTED0.00 sdetails
#10ACCEPTED0.00 sdetails
#11ACCEPTED0.00 sdetails
#12ACCEPTED0.00 sdetails
#13ACCEPTED0.00 sdetails

Compiler report

input/code.cpp: In function 'void Test()':
input/code.cpp:138:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  138 |     freopen("temp\\in.txt", "r", stdin);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~
input/code.cpp: In member function 'void Point::Input()':
input/code.cpp:24:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   24 |         scanf("%lf%lf", &x_, &y_);
      |         ~~~~~^~~~~~~~~~~~~~~~~~~~

Code

#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
const int N=10005;
const double EPS = 1e-8, INF=1e20, PI = acos(-1.0);

inline int Sign(const double& x)
{
    if(fabs(x) < EPS)   return 0;
    if(x < 0)           return -1;
    else                return 1;
}

struct Point
{
    double x_, y_;
    Point(){}
    Point(double x, double y)
    {
        x_ = x;
        y_ = y;
    }
    void Input() {
        scanf("%lf%lf", &x_, &y_);
    }

    bool operator == (const Point& P)const {
        return Sign(x_ - P.x_) == 0 && Sign(y_ - P.y_) == 0;
    }
    bool operator < (const Point& P)const {
        return Sign(x_ - P.x_) == 0? Sign(y_ - P.y_)<0 : x_<P.x_;
    }
    double operator ^ (const Point& P)const {
        return x_*P.y_ - y_*P.x_;
    }
    double operator * (const Point& P)const {
        return x_*P.x_ + y_*P.y_;
    }
    Point operator + (const Point& P)const {
        return Point(x_+P.x_, y_+P.y_);
    }
    Point operator - (const Point& P)const {
        return Point(x_-P.x_, y_-P.y_);
    }
    Point operator * (const double& k)const {
        return Point(x_*k, y_*k);
    }
    Point operator / (const double& k)const {
        return Point(x_/k, y_/k);
    }

    double len() {
        return hypot(x_, y_);
    }
};

struct Line
{
    Point s_, e_;
    Line(){}
    Line(Point s, Point e)
    {
        s_ = s;
        e_ = e;
    }
    Line(Point p, double angle)
    {
        s_ = p;
        if(Sign(angle - PI/2) == 0) {
            e_ = (s_ + Point(0, 1));
        } else {
            e_ = (s_ + Point(1, tan(angle)));
        }
    }
    // 3(O) 2(R) 1(L)
    int Relation(Point p) 
    {
        int c = Sign((p-s_)^(e_-s_));
        if(c < 0)       return 1;
        else if(c > 0)  return 2;
        else            return 3;
    }
    bool OnSeg(Point p) {
        return Sign((p-s_)^(e_-s_)) == 0 && Sign((p-s_)^(p-e_)) <= 0;
    }
};


struct Polygon
{
    int n_;
    Point p_[N];
    Line l_[N];
    void Input(int n)
    {
        n_ = n;
        for(int i=0; i<n_; i++)
            p_[i].Input();
        InitLines();
    }
    void InitLines()
    {
        for(int i=0; i<n_; i++)
            l_[i] = Line(p_[i], p_[(i+1)%n_]);
    }

    double Area()
    {
        double ret = 0;
        for(int i=0; i<n_; i++)
            ret += (p_[i] ^ p_[(i+1)%n_]);
        return fabs(ret)/2;
    }
    // 3(P) 2(E) 1(I) 0(O)
    int Relation(Point p)
    {
        for(int i=0; i<n_; i++)
            if(p_[i] == p)      return 3;
        for(int i=0; i<n_; i++)
            if(l_[i].OnSeg(p))  return 2;
        int cnt = 0;
        for(int i=0; i<n_; i++)
        {
            int j = (i+1)%n_;
            int k = Sign((p-p_[j])^(p_[i]-p_[j]));
            int u = Sign(p_[i].y_ - p.y_);
            int v = Sign(p_[j].y_ - p.y_);
            if(k > 0 && u < 0 && v >= 0) cnt++;
            if(k < 0 && v < 0 && u >= 0) cnt--;
        }
        return cnt != 0;
    }
};


void Test()
{
    freopen("temp\\in.txt", "r", stdin);
}
int main()
{
    // Test();
    int n, m;
    cin >> n >> m;
    Polygon G;
    G.Input(n);

    while(m--)
    {
        Point x;
        x.Input();
        int r = G.Relation(x);
        switch (r)
        {
        case 0:
            cout << "OUTSIDE" <<endl;
            break;
        case 1:
            cout << "INSIDE" <<endl;
            break;
        default:
            cout << "BOUNDARY" <<endl;
            break;
        }
    }
    return 0;
}

Test details

Test 1

Verdict:

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:

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

correct output
INSIDE

user output
BOUNDARY

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