Task: | Point in Polygon |
Sender: | Niilo |
Submission time: | 2024-11-11 16:27:14 +0200 |
Language: | C++ (C++17) |
Status: | READY |
Result: | ACCEPTED |
test | verdict | time | |
---|---|---|---|
#1 | ACCEPTED | 0.01 s | details |
#2 | ACCEPTED | 0.01 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 | ACCEPTED | 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 | ACCEPTED | 0.00 s | details |
#13 | ACCEPTED | 0.00 s | details |
Code
#include <bits/stdc++.h> using namespace std; #define rep(i, a, b) for(int i=a;i<(b);++i) #define all(x) begin(x),end(x) #define sz(x) int((x).size()) using ll = long long; using pii = pair<int,int>; using vi = vector<int>; /** * Author: Ulf Lundstrom * Date: 2009-02-26 * License: CC0 * Source: My head with inspiration from tinyKACTL * Description: Class to handle points in the plane. * T can be e.g. double or long long. (Avoid int.) * Status: Works fine, used a lot */ template <class T> int sgn(T x) { return (x > 0) - (x < 0); } template<class T> struct Point { typedef Point P; T x, y; explicit Point(T x=0, T y=0) : x(x), y(y) {} bool operator<(P p) const { return tie(x,y) < tie(p.x,p.y); } bool operator==(P p) const { return tie(x,y)==tie(p.x,p.y); } P operator+(P p) const { return P(x+p.x, y+p.y); } P operator-(P p) const { return P(x-p.x, y-p.y); } P operator*(T d) const { return P(x*d, y*d); } P operator/(T d) const { return P(x/d, y/d); } T dot(P p) const { return x*p.x + y*p.y; } T cross(P p) const { return x*p.y - y*p.x; } T cross(P a, P b) const { return (a-*this).cross(b-*this); } T dist2() const { return x*x + y*y; } double dist() const { return sqrt((double)dist2()); } // angle to x-axis in interval [-pi, pi] double angle() const { return atan2(y, x); } P unit() const { return *this/dist(); } // makes dist()=1 P perp() const { return P(-y, x); } // rotates +90 degrees P normal() const { return perp().unit(); } // returns point rotated 'a' radians ccw around the origin P rotate(double a) const { return P(x*cos(a)-y*sin(a),x*sin(a)+y*cos(a)); } friend istream& operator>>(istream& os, P& p) { return os >> p.x >> p.y; } friend ostream& operator<<(ostream& os, P p) { return os << '(' << p.x << ',' << p.y << ')'; } }; using pd = Point<ll>; template<class P> bool onSegment(P s, P e, P p) { return p.cross(s, e) == 0 && (s - p).dot(e - p) <= 0; } /** * Author: Victor Lecomte, chilli * Date: 2019-04-26 * License: CC0 * Source: https://vlecomte.github.io/cp-geo.pdf * Description: Returns true if p lies within the polygon. If strict is true, * it returns false for points on the boundary. The algorithm uses * products in intermediate steps so watch out for overflow. * Time: O(n) * Usage: * vector<P> v = {P{4,4}, P{1,2}, P{2,1}}; * bool in = inPolygon(v, P{3, 3}, false); * Status: stress-tested and tested on kattis:pointinpolygon */ template<class P> void inPolygon(vector<P> &p, P a) { int cnt = 0, n = sz(p); rep(i,0,n) { P q = p[(i + 1) % n]; if (onSegment(p[i], q, a)) { cout << "BOUNDARY\n"; return; } //or: if (segDist(p[i], q, a) <= eps) return !strict; cnt ^= ((a.y<p[i].y) - (a.y<q.y)) * a.cross(p[i], q) > 0; } cout << (cnt ? "INSIDE\n" : "OUTSIDE\n"); } int main() { int n, m; cin >> n >> m; vector<pd> P(n); rep(i,0,n) { cin >> P[i]; } rep(i,0,m) { pd p; cin >> p; inPolygon(P,p); } }
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: 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 |