Task: | Point in Polygon |
Sender: | htoik |
Submission time: | 2024-11-11 17:47:57 +0200 |
Language: | C++ (C++20) |
Status: | READY |
Result: | WRONG ANSWER |
test | verdict | time | |
---|---|---|---|
#1 | WRONG ANSWER | 0.00 s | details |
#2 | WRONG ANSWER | 0.01 s | details |
#3 | WRONG ANSWER | 0.00 s | details |
#4 | ACCEPTED | 0.00 s | details |
#5 | WRONG ANSWER | 0.00 s | details |
#6 | WRONG ANSWER | 0.00 s | details |
#7 | WRONG ANSWER | 0.00 s | details |
#8 | WRONG ANSWER | 0.00 s | details |
#9 | ACCEPTED | 0.00 s | details |
#10 | WRONG ANSWER | 0.00 s | details |
#11 | ACCEPTED | 0.00 s | details |
#12 | WRONG ANSWER | 0.00 s | details |
#13 | ACCEPTED | 0.00 s | details |
Compiler report
input/code.cpp: In function 'int main()': input/code.cpp:58:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<pt>::size_type' {aka 'long unsigned int'} [-Wsign-compare] 58 | for(int i=0; i<ps.size(); i++){ | ~^~~~~~~~~~ input/code.cpp:60:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<pt>::size_type' {aka 'long unsigned int'} [-Wsign-compare] 60 | pt b = (i == ps.size() -1 ? ps[0] : ps[i+1]); | ~~^~~~~~~~~~~~~~~
Code
#include <bits/stdc++.h> using namespace std; typedef long long ll; typedef unsigned long long ull; struct pt{ ll x; ll y; }; pt operator+(const pt& a, const pt& b){ return pt{.x=a.x+b.x, .y=a.y+b.y}; }; pt operator-(const pt& a, const pt& b){ return pt{.x=a.x-b.x, .y=a.y-b.y}; }; bool operator==(const pt& a, const pt& b){ return a.x == b.x && a.y == b.y; }; ostream& operator<<(ostream& os, const pt& a){ return os << "(" << a.x << "," << a.y << ")"; } ll cross(pt p1, pt p2){ return p1.x*p2.y - p1.y*p2.x; } ll orient(pt a, pt b, pt c) { return cross(b-a, c-a); } ll dot(pt a, pt b){ return a.x*b.x+a.y*b.y; } int isintersect(pt p, pt a, pt b){ if(a.y > b.y) swap(a.y, b.y); // int r = a.x >= p.x && b.x >= p.x && a.y <= p.y && b.y >= p.y; pt ray{.x=1, .y=0}; // int r = a.x >= p.x && b.x >= p.x && a.y <= p.y && b.y >= p.y; pt d1 = a - p; pt d2 = b - p; ll dp = dot(d1, d2); int r = cross(ray,d1) * cross(ray,d2) < 0; int r2 = (dp <= 0 && cross(d1,d2) == 0 ? 10 : 0); // if(r2){ // cout << "here: " << d1 << " " << d2 << " " << dp << " " << cross(d1,d2) << " " << r2 << "\n"; // } return r + r2; } int main() { ios::sync_with_stdio(0); cin.tie(0); int n,m; cin >> n >> m; vector<pt> ps; ps.reserve(n); for(int i=0; i<n; i++){ ll x, y; cin >> x >> y; ps.push_back({x,y}); } for(int k=0; k<m; k++){ pt p; cin >> p.x >> p.y; int ci = 0; int br = 0; for(int i=0; i<ps.size(); i++){ pt a = ps[i]; pt b = (i == ps.size() -1 ? ps[0] : ps[i+1]); // cout << "this: " << i << " " << a << " " << b << endl; auto r = (isintersect(p,a,b)); ci += r; if(r > 1){ cout << "BOUNDARY\n"; br = 1; break; } } if(br)continue; cout << (ci % 2 == 0 ? "OUTSIDE" : "INSIDE") << "\n"; } }
Test details
Test 1
Verdict: WRONG ANSWER
input |
---|
100 1000 -7 -19 91 77 100 100 64 60 ... |
correct output |
---|
INSIDE OUTSIDE INSIDE INSIDE INSIDE ... |
user output |
---|
OUTSIDE OUTSIDE OUTSIDE OUTSIDE OUTSIDE ... |
Test 2
Verdict: WRONG ANSWER
input |
---|
1000 1000 365625896 -113418831 278762563 38777445 250367343 -96991975 175866909 -129766978 ... |
correct output |
---|
OUTSIDE OUTSIDE INSIDE OUTSIDE OUTSIDE ... |
user output |
---|
OUTSIDE OUTSIDE OUTSIDE OUTSIDE OUTSIDE ... |
Test 3
Verdict: WRONG ANSWER
input |
---|
4 1 1 5 5 5 5 1 1 1 ... |
correct output |
---|
INSIDE |
user output |
---|
OUTSIDE |
Test 4
Verdict: ACCEPTED
input |
---|
4 1 1 5 5 5 5 1 1 1 ... |
correct output |
---|
OUTSIDE |
user output |
---|
OUTSIDE |
Test 5
Verdict: WRONG ANSWER
input |
---|
4 1 1 100 2 50 1 20 0 50 ... |
correct output |
---|
INSIDE |
user output |
---|
BOUNDARY |
Test 6
Verdict: WRONG ANSWER
input |
---|
8 1 0 0 0 2 1 1 2 2 ... |
correct output |
---|
INSIDE |
user output |
---|
BOUNDARY |
Test 7
Verdict: WRONG ANSWER
input |
---|
4 4 0 0 3 0 3 4 0 4 ... |
correct output |
---|
INSIDE BOUNDARY OUTSIDE BOUNDARY |
user output |
---|
OUTSIDE BOUNDARY OUTSIDE BOUNDARY |
Test 8
Verdict: WRONG ANSWER
input |
---|
6 1 0 0 0 2 3 1 2 2 ... |
correct output |
---|
INSIDE |
user output |
---|
OUTSIDE |
Test 9
Verdict: ACCEPTED
input |
---|
3 1 0 0 1 1000000000 -3 0 1 1 |
correct output |
---|
OUTSIDE |
user output |
---|
OUTSIDE |
Test 10
Verdict: WRONG ANSWER
input |
---|
3 1 -100000 0 -1000000000 -999999999 1000000000 1000000000 0 0 |
correct output |
---|
OUTSIDE |
user output |
---|
INSIDE |
Test 11
Verdict: ACCEPTED
input |
---|
3 1 -100000 0 -999999999 -1000000000 1000 1000 0 0 |
correct output |
---|
INSIDE |
user output |
---|
INSIDE |
Test 12
Verdict: WRONG ANSWER
input |
---|
4 1 -4 1 -6 1 -6 -1 -4 -1 ... |
correct output |
---|
INSIDE |
user output |
---|
OUTSIDE |
Test 13
Verdict: ACCEPTED
input |
---|
3 1 0 10 0 -10 10 0 1 0 |
correct output |
---|
INSIDE |
user output |
---|
INSIDE |