CSES - Aalto Competitive Programming 2024 - wk10 - Mon - Results
Submission details
Task:Point in Polygon
Sender:snude
Submission time:2024-11-11 17:49:53 +0200
Language:C++ (C++11)
Status:READY
Result:
Test results
testverdicttime
#1ACCEPTED0.01 sdetails
#2ACCEPTED0.07 sdetails
#3ACCEPTED0.00 sdetails
#4ACCEPTED0.00 sdetails
#5ACCEPTED0.00 sdetails
#6ACCEPTED0.00 sdetails
#70.00 sdetails
#8ACCEPTED0.00 sdetails
#9ACCEPTED0.00 sdetails
#10ACCEPTED0.00 sdetails
#11ACCEPTED0.00 sdetails
#120.00 sdetails
#13ACCEPTED0.00 sdetails

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:

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:

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