CSES - Aalto Competitive Programming 2024 - wk10 - Mon - Results
Submission details
Task:Point in Polygon
Sender:Rasse
Submission time:2024-11-11 16:26:42 +0200
Language:C++ (C++17)
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

Compiler report

input/code.cpp: In function 'void solve()':
input/code.cpp:48:23: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<std::complex<long long int>, std::complex<long long int> > >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   48 |     for (int i = 0; i < lines.size(); i++)
      |                     ~~^~~~~~~~~~~~~~
input/code.cpp:63:27: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<std::complex<long long int>, std::complex<long long int> > >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   63 |         for (int i = 0; i < lines.size(); i++)
      |                         ~~^~~~~~~~~~~~~~

Code

#include <iostream>
#include <vector>
#include <array>
#include <string>
#include <algorithm>
#include <numeric>
#include <unordered_map>
#include <unordered_set>
#include <queue>
#include <climits>
#include <cmath>
#include <functional>
#include <type_traits>
#include <fstream>
#include <bitset>
#include <complex>
 
#define int long long
using namespace std;
 
//#define cross(x, y) ((x).real()*(y).imag()-(x).imag()*(y).real()) 
#define cross(x, y) (((x)*conj(y)).imag())
#define sign(v) ((0 < (v)) - ((v) < 0))
 
void solve()
{
    int n, m;
    cin >> n >> m;
 
    vector<pair<complex<int>, complex<int>>> lines(n);
 
    int x1, y1;
    cin >> x1 >> y1;
    complex<int> first = {x1, y1};
    complex<int> prev = first;
 
    for (int i = 0; i < n-1; i++)
    {
        int x, y;
        cin >> x >> y;
        complex<int> t = {x, y};
 
        lines[i] = {prev, t};
 
        prev = t;
    }
    lines[n-1] = {prev, first};
    for (int i = 0; i < lines.size(); i++)
    {
        if (lines[i].first.imag() > lines[i].second.imag())
            swap(lines[i].first, lines[i].second);
    }
 
    for (int i = 0; i < m; i++)
    {
        int x, y;
        cin >> x >> y;
        complex<int> test = {x, y};
 
        bool boundary = false;
        int intersections = 0;
 
        for (int i = 0; i < lines.size(); i++)
        {
            if (lines[i].first.imag() == lines[i].second.imag())
            {
                if (lines[i].first.real() > lines[i].second.real())
                    swap(lines[i].first, lines[i].second);
 
                if (lines[i].first.imag() == test.imag() && lines[i].first.real() <= x && lines[i].second.real() >= x)
                {
                    boundary = true;
                    break;
                }
                continue;
            }
 
            if (lines[i].first.imag() > test.imag() || lines[i].second.imag() < test.imag())
                continue;
 
            int c = cross(lines[i].second - lines[i].first, test - lines[i].first);
            if (c == 0)
            {
                boundary = true;
                break;
            }
 
            if (lines[i].first.imag() == test.imag())
                continue;
 
            
            if (c > 0)
                intersections++;
        }
 
        if (boundary)
        {
            cout << "BOUNDARY\n";
            continue;
        }
 
        if (intersections % 2 == 0)
        {
            cout << "OUTSIDE\n";
        }
        else
        {
            cout << "INSIDE\n";
        }
    }
 
}
 
 
signed main()
{
    ios::sync_with_stdio(0);
    //cin.tie(0);
 
    int t = 1;
 
    //cin >> t;
    //ifstream f("testcase.txt");
    //cin.rdbuf(f.rdbuf());
 
    for (int i = 0; i < t; i++)
        solve();
}

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
...
Truncated

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
...
Truncated

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