CSES - E4590 2016 1 - Results
Submission details
Task:Taxing
Sender:warbaque
Submission time:2016-09-17 15:56:56 +0300
Language:C++
Status:READY
Result:
Test results
testverdicttime
#10.06 sdetails
#20.14 sdetails
#30.05 sdetails
#40.12 sdetails
#50.05 sdetails

Code

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <vector>

struct Point
{
    Point() {};
    Point(int x, int y): x(x), y(y) {};
    int x;
    int y;
};

int contains(std::vector<Point>& hull, Point p)
{
    using namespace std;
    int result = 0;
    int r = 1;

    unsigned j = hull.size() - 1;
    for (unsigned i=0; i < hull.size(); j = i++)
    {
        //(pi.y > p.y) != (pj.y > p.y))
        auto pi = hull[i];
        auto pj = hull[j];
        r *= (((pj.x - pi.x) / (pj.y - pi.y) * (p.y - pi.y) + pi.x) - p.x);

        if ((hull[i].y > p.y) != (hull[j].y > p.y) &&
            (p.x < (hull[j].x - hull[i].x) / (hull[j].y - hull[i].y) *
            (p.y - hull[i].y) + hull[i].x))
            result = !result;
    }
    return r;
}

int main() {
    using namespace std;
    ios::sync_with_stdio(false);

    int x,y,n;
    cin >> n;

    vector<Point> border;
    for (int i=0; i<n; ++i) {
        cin >> x >> y;
        border.emplace_back(x, y);
    }

    cin >> n;

    for (int i=0; i<n; ++i) {
        cin >> x >> y;
        int c = contains(border, Point(x,y));
        cout << (c > 0 ? "inside" : c < 0 ? "outside" : "border") << endl;
    }
}

Test details

Test 1

Verdict:

input
9
0 10
-2 0
-1 -4
-7 1
...

correct output
inside
inside
inside
outside
inside
...

user output
border
border
inside
inside
inside
...

Test 2

Verdict:

input
99
13 4
14 8
10 5
9 6
...

correct output
inside
border
inside
outside
inside
...

user output
(empty)

Test 3

Verdict:

input
99
50 33
28 57
80 28
37 60
...

correct output
outside
inside
outside
inside
outside
...

user output
border
border
border
border
border
...

Test 4

Verdict:

input
999
87 -3
91 5
77 -7
41 -18
...

correct output
inside
outside
inside
outside
outside
...

user output
(empty)

Test 5

Verdict:

input
999
915887 494689
950720 189774
823677 443456
879821 402443
...

correct output
outside
outside
inside
inside
inside
...

user output
border
border
border
border
border
...