Task: | Point in Polygon |
Sender: | snude |
Submission time: | 2024-11-11 17:49:53 +0200 |
Language: | C++ (C++11) |
Status: | READY |
Result: | WRONG ANSWER |
test | verdict | time | |
---|---|---|---|
#1 | ACCEPTED | 0.01 s | details |
#2 | ACCEPTED | 0.07 s | details |
#3 | ACCEPTED | 0.00 s | details |
#4 | ACCEPTED | 0.00 s | details |
#5 | ACCEPTED | 0.00 s | details |
#6 | ACCEPTED | 0.00 s | details |
#7 | WRONG ANSWER | 0.00 s | details |
#8 | ACCEPTED | 0.00 s | details |
#9 | ACCEPTED | 0.00 s | details |
#10 | ACCEPTED | 0.00 s | details |
#11 | ACCEPTED | 0.00 s | details |
#12 | WRONG ANSWER | 0.00 s | details |
#13 | ACCEPTED | 0.00 s | details |
Code
#include <bits/stdc++.h> #include <climits> #include <cmath> using namespace std; using ll = long long; typedef long long C; typedef complex<C> P; #define X real() #define Y imag() // Debug printing #ifdef DEBUG #define deb(fmt, args...) printf("DEBUG: %d: " fmt, __LINE__, ##args) #define debug_print(fmt, args...) printf(fmt, ##args) #else #define deb(fmt, args...) #define debug_print(fmt, args...) #endif void print_array(vector<int> in, const string title = "Vector") { debug_print("DEBUG: %s [\nDEBUG: ", title.c_str()); for (unsigned int i = 0; i < in.size(); i++) { debug_print("%d ", in[i]); } debug_print("\nDEBUG: ] END\n"); } void print_matrix(vector<vector<int> > in, const string title = "Matrix") { debug_print("DEBUG: %s [\nDEBUG: ", title.c_str()); for (unsigned int i = 0; i < in.size(); i++) { for (unsigned int j = 0; j < in[i].size(); j++) { debug_print("%d ", in[i][j]); } debug_print("\nDEBUG: "); } debug_print("DEBUG: ] END\n"); } double angle(int x1, int y1, int x2, int y2) { double dot = x1 * x2 + y1 * y2; double cross = x1 * y2 - y1 * x2; return atan2(cross, dot); } double dist(int x1, int y1, int x2, int y2) { return sqrt((x1 - x2) * (x1 - x2) + (y1 - y2) * (y1 - y2)); } int intersect(P a, P b, P c, P d) { if (a == c || a == d) { return 1; } // ll cross = (conj(v1)*v2).Y; ll x1 = a.X, y1 = a.Y, x2 = b.X, y2 = b.Y; ll x3 = c.X, y3 = c.Y, x4 = d.X, y4 = d.Y; double err = 0.00000000000001; double ad = dist(x1, y1, x4, y4); double ca = dist(x1, y1, x3, y3); double cd = dist(x3, y3, x4, y4); if (abs(ca + ad - cd) <= err) { return 1; } double t1 = (1.0 * (x1 - x3) * (y3 - y4) - (y1 - y3) * (x3 - x4)); double t2 = (1.0 * (x1 - x2) * (y3 - y4) - (y1 - y2) * (x3 - x4)); double u1 = -(1.0 * (x1 - x2) * (y1 - y3) - (y1 - y2) * (x1 - x3)); double u2 = (1.0 * (x1 - x2) * (y3 - y4) - (y1 - y2) * (x3 - x4)); double t = t1 / t2; double u = u1 / u2; if (u >= -err && u <= 1.0 + err && t >= -err && t <= 1.0 + err) { return 2; } return 0; } int main(int argc, char *argv[]) { ios::sync_with_stdio(0); cin.tie(0); // Read the input parameters int n, m; cin >> n >> m; vector<P> polygon(n + 1); int x, y; int mx = INT_MIN, my = INT_MIN; for (int i = 0; i < n; i++) { cin >> x >> y; if (x > my) { mx = x; } if (y > my) { my = y; } polygon[i] = { x, y }; } polygon[n] = polygon[0]; for (int i = 0; i < m; i++) { ll x1, y1; cin >> x1 >> y1; P a = { x1, y1 }; P b = { mx + 1, my + 1 }; int num = 0; bool print = true; for (int j = 0; j < n; j++) { // deb("j: %d\n", j); int res = intersect(a, b, polygon[j], polygon[j + 1]); if (res == 1) { cout << "BOUNDARY\n"; print = false; break; } if (res == 2) { num++; } } // deb("num %d\n", num); if (print && num % 2 == 1) { cout << "INSIDE\n"; } if (print && num % 2 == 0) { cout << "OUTSIDE\n"; } } }
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: 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: 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: 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 |