Task: | Point in Polygon |
Sender: | AleksandrPolitov |
Submission time: | 2024-11-11 16:26:36 +0200 |
Language: | C++ (C++20) |
Status: | READY |
Result: | ACCEPTED |
test | verdict | time | |
---|---|---|---|
#1 | ACCEPTED | 0.01 s | details |
#2 | ACCEPTED | 0.08 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
#ifdef ONPC #define _GLIBCXX_DEBUG #endif #include <bits/stdc++.h> #define char unsigned char #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() #define eb emplace_back #define mp make_pair #define mt make_tuple #define fi first #define se second #define pb push_back #define LSOne(S) ((S) & -(S)) using namespace std; // mt19937 rnd(239); mt19937 rnd(chrono::steady_clock::now().time_since_epoch().count()); template <typename T> int sgn(T x) { return (T(0) < x) - (x < T(0)); } typedef long double T; typedef complex<T> pt; #define X real() #define Y imag() template<class T> istream& operator>> (istream& is, complex<T>& p) { T value; is >> value; p.real(value); is >> value; p.imag(value); return is; } typedef long long ll; typedef long double ld; using pi = pair<ll, ll>; using vi = vector<ll>; template <class T> using pq = priority_queue<T>; template <class T> using pqg = priority_queue<T, vector<T>, greater<T>>; int popcnt(int x) { return __builtin_popcount(x); } int popcnt(ll x) { return __builtin_popcountll(x); } #define MIN(v) *min_element(all(v)) #define MAX(v) *max_element(all(v)) #define LB(c, x) distance((c).begin(), lower_bound(all(c), (x))) #define UB(c, x) distance((c).begin(), upper_bound(all(c), (x))) void __print(int x) {cerr << x;} void __print(long x) {cerr << x;} void __print(long long x) {cerr << x;} void __print(unsigned x) {cerr << x;} void __print(unsigned long x) {cerr << x;} void __print(unsigned long long x) {cerr << x;} void __print(float x) {cerr << x;} void __print(double x) {cerr << x;} void __print(long double x) {cerr << x;} void __print(char x) {cerr << '\'' << x << '\'';} void __print(const char *x) {cerr << '\"' << x << '\"';} void __print(const string &x) {cerr << '\"' << x << '\"';} void __print(bool x) {cerr << (x ? "true" : "false");} template<typename T, typename V> void __print(const pair<T, V> &x) {cerr << '{'; __print(x.first); cerr << ", "; __print(x.second); cerr << '}';} template<typename T> void __print(const T &x) {int f = 0; cerr << '{'; for (auto &i: x) cerr << (f++ ? ", " : ""), __print(i); cerr << "}";} void _print() {cerr << "]\n";} template <typename T, typename... V> void _print(T t, V... v) {__print(t); if (sizeof...(v)) cerr << ", "; _print(v...);} #ifdef DEBUG #define dbg(x...) cerr << "\e[91m"<<__func__<<":"<<__LINE__<<" [" << #x << "] = ["; _print(x); cerr << "\e[39m" << endl; #else #define dbg(x...) #endif template<typename S, typename T = S> void chmin(S &s, T t) {s = s < t ? s : t;} template<typename S, typename T = S> void chmax(S &s, T t) {s = s > t ? s : t;} const int INF = 1e9; // 10^9 = 1B is < 2^31-1 const ll LLINF = 4e18; // 4*10^18 is < 2^63-1 const double EPS = 1e-9; const ll MOD = 1e9+7; T sq(pt p) {return p.X*p.X + p.Y*p.Y;} T abs(pt p) {return sqrt(sq(p));} bool half(pt p) { return p.Y > 0 || (p.Y == 0 && p.X < 0); } // check if p is on [pi, 0) pt translate(pt v, pt p) { return v+p; } // translate 'v' with 'p' pt scale(pt c, T factor, pt v) { return c+factor*(v-c); } // scale an object 'v' by a ratio 'factor' around a center 'c' pt rot(pt p, T a) { return p*polar(1.0L, a); } // rotate around point 'p' with a rad 'a' pt perp(pt p) { return {-p.Y, p.X}; } // rotate by 90 around the origin pt linearTransfo(pt p, pt q, pt r, pt fp, pt fq) { return fp + (r-p) * (fq-fp) / (q-p); } // linear tranfomation f(r)=f(p)+(r-p)*((f(q)-f(p))/(q-p)) //T dot(pt v, pt w) { return v.X*w.X + v.Y*w.Y; } // dot product T dot(pt v, pt w) {return (conj(v)*w).X;} // using trick bool isPerp(pt v, pt w) { return dot(v,w) == 0; } // check if 'v' and 'w' are perpendicular T angle(pt v, pt w) { return acos(clamp<T>(dot(v,w) / abs(v) / abs(w), -1.0, 1.0)); } // get angle between 'v' and 'w' vectors //T cross(pt v, pt w) { return v.X*w.Y - v.Y*w.X; } // cross product of 'v' and 'w' T cross(pt v, pt w) {return (conj(v)*w).Y;} // using trick T orient(pt a, pt b, pt c) { return cross(b-a,c-a); } // returns // positive if c is to the left of ab // negative if c is to the left of ab // 0 if a,b,c are co-linear bool inAngle(pt a, pt b, pt c, pt p) { // check if p is in angle formed by bAc assert(orient(a,b,c) != 0); if (orient(a,b,c) < 0) swap(b,c); return orient(a,b,p) >= 0 && orient(a,c,p) <= 0; } T orientedAngle(pt a, pt b, pt c) { // TODO if (orient(a,b,c) >= 0) return angle(b-a, c-a); else return 2*M_PI - angle(b-a, c-a); } bool isConvex(vector<pt> p) { // check if polygon P is convex bool hasPos=false, hasNeg=false; for (int i=0, n=p.size(); i<n; i++) { int o = orient(p[i], p[(i+1)%n], p[(i+2)%n]); if (o > 0) hasPos = true; if (o < 0) hasNeg = true; } return !(hasPos && hasNeg); } void polarSort(vector<pt> &v) { // polar sort around the origin with closer to origin first sort(v.begin(), v.end(), [&](pt a, pt b) { if(half(a)<half(b)) return true; if(0.0L<cross(a,b)) return true; return sq(a)<sq(b); }); } void polarSortAround(pt o, vector<pt> &v) { // polar sort around o with closer to origin first sort(v.begin(), v.end(), [&](pt a, pt b) { if(half(b-o)<half(a-o)) return true; return 0.0L<cross(a-o, b-o); }); } struct line { pt v; T c; // From direction vector v and offset c line(pt v, T c) : v(v), c(c) {} // From equation ax+by=c line(T a, T b, T c) : v(pt{b,-a}), c(c) {} // From points P and Q line(pt p, pt q) : v(q-p), c(cross(v,p)) {} T side(pt p) {return cross(v,p)-c;} // which side of a line point p lies on T dist(pt p) {return abs(side(p)) / abs(v);} // distance between point p and the line T sqDist(pt p) {return side(p)*side(p) / (T)sq(v);} // square distance line perpThrough(pt p) {return {p, p + perp(v)};} // perpendicular line that goes through p bool cmpProj(pt p, pt q) {return dot(v,p) < dot(v,q);} // order of two points in order of the line line translate(pt t) {return {v, c + cross(v,t)};} // translate line with vector 't' line shiftLeft(T dist) {return {v, c + dist*abs(v)};} // line that is shifted by 'dist' to the left of the line pt proj(pt p) {return p - perp(v)*side(p)/sq(v);} // point on line that is closest to 'p' pt refl(pt p) {return p - perp(v)*2.0L*side(p)/sq(v);} // reflection of point 'p' around the line }; bool inter(line l1, line l2, pt &out) { // return true iff lines l1 and l2 are not parallel and saves to 'out' the point of intersection T d = cross(l1.v, l2.v); if (d == 0) return false; out = (l2.v*l1.c - l1.v*l2.c) / d; // requires floating-point coordinates return true; } line bisector(line l1, line l2, bool interior) { // bisector line assert(cross(l1.v, l2.v) != 0); // l1 and l2 cannot be parallel! T sign = interior ? 1 : -1; return {l2.v/abs(l2.v) + l1.v/abs(l1.v) * sign, l2.c/abs(l2.v) + l1.c/abs(l1.v) * sign}; } bool inDisk(pt a, pt b, pt p) { // check if 'p' is inside of disc with diameter ab return dot(a-p, b-p) <= 0; } bool onSegment(pt a, pt b, pt p) { // check if 'p' is on segment ab return orient(a,b,p) == 0 && inDisk(a,b,p); } bool properInter(pt a, pt b, pt c, pt d, pt &out) { // intersection is one single point which is not an endpoint of either segment // returns true iff there is point of intersection and saves to 'out' the point of intersection T oa = orient(c,d,a), ob = orient(c,d,b), oc = orient(a,b,c), od = orient(a,b,d); // Proper intersection exists iff opposite signs if (oa*ob < 0 && oc*od < 0) { out = (a*ob - b*oa) / (ob-oa); return true; } return false; } struct cmpX { bool operator()(const pt &a, const pt &b) const { return make_pair(a.X, a.Y) < make_pair(b.X, b.Y); } }; set<pt,cmpX> inters(pt a, pt b, pt c, pt d) { // general intersection // returns set of points pt out; if (properInter(a,b,c,d,out)) return {out}; set<pt,cmpX> s; if (onSegment(c,d,a)) s.insert(a); if (onSegment(c,d,b)) s.insert(b); if (onSegment(a,b,c)) s.insert(c); if (onSegment(a,b,d)) s.insert(d); return s; } T segPoint(pt a, pt b, pt p) { // return min distance from 'p' to segment ab if (a != b) { line l(a,b); if (l.cmpProj(a,p) && l.cmpProj(p,b)) // if closest to projection return l.dist(p); // output distance to line } return min(abs(p-a), abs(p-b)); // otherwise distance to A or B } T segSeg(pt a, pt b, pt c, pt d) { // returns min distance between two segments ab and cd pt dummy; if (properInter(a,b,c,d,dummy)) return 0; return min({segPoint(a,b,c), segPoint(a,b,d), segPoint(c,d,a), segPoint(c,d,b)}); } T areaTriangle(pt a, pt b, pt c) { // area of triangle abc return abs(cross(b-a, c-a)) / 2.0L; } T areaPolygon(vector<pt> p) { // area of polygon p T area = 0.0; for (int i = 0, n = p.size(); i < n; i++) { area += cross(p[i], p[(i+1)%n]); // wrap back to 0 if i == n-1 } return abs(area) / 2.0L; } bool above(pt a, pt p) { // true if P at least as high as A (blue part) return p.Y >= a.Y; } bool crossesRay(pt a, pt p, pt q) { // check if [PQ] crosses ray from A return (above(a,q) - above(a,p)) * orient(a,p,q) > 0; } bool inPolygon(vector<pt> p, pt a, bool strict = true) { // if strict, returns false when A is on the boundary int numCrossings = 0; for (int i = 0, n = p.size(); i < n; i++) { if (onSegment(p[i], p[(i+1)%n], a)) return !strict; numCrossings += crossesRay(a, p[i], p[(i+1)%n]); } return numCrossings & 1; // inside if odd number of crossings } T angleTravelled(pt a, pt p, pt q) { // remainder ensures the value is in [-pi,pi] return remainder(arg(q-a) - arg(p-a), 2*M_PI); } int windingNumber(vector<pt> p, pt a) { // NaN if point on the edge T ampli = 0; for (int i = 0, n = p.size(); i < n; i++) ampli += angleTravelled(a, p[i], p[(i+1)%n]); return round(ampli / (2*M_PI)); } pt circumCenter(pt a, pt b, pt c) { b = b-a, c = c-a; // consider coordinates relative to A assert(cross(b,c) != 0); // no circumcircle if A,B,C aligned return a + perp(b*sq(c) - c*sq(b))/cross(b,c)/2.0L; } int circleLine(pt o, T r, line l, pair<pt,pt> &out) { // returns number of intersections of line 'l' and the circle with center 'o' and radius 'r', saves points of intersection to 'out' T h2 = r*r - l.sqDist(o); if (h2 >= 0) { // the line touches the circle pt p = l.proj(o); // point P pt h = l.v*sqrt(h2)/abs(l.v); // vector parallel to l, of length h out = {p-h, p+h}; } return 1 + sgn(h2); } int circleCircle(pt o1, T r1, pt o2, T r2, pair<pt,pt> &out) { // returns number of intersections of two circles, saves points of intersection to 'out' pt d=o2-o1; T d2=sq(d); if (d2 == 0) {assert(r1 != r2); return 0;} // concentric circles T pd = (d2 + r1*r1 - r2*r2)/2; // = |O_1P| * d T h2 = r1*r1 - pd*pd/d2; // = hˆ2 if (h2 >= 0) { pt p = o1 + d*pd/d2, h = perp(d)*sqrt(h2/d2); out = {p-h, p+h}; } return 1 + sgn(h2); } int tangents(pt o1, T r1, pt o2, T r2, bool inner, vector<pair<pt,pt>> &out) { // returns tangents to two circles, saves it to 'out' the points on circles if (inner) r2 = -r2; pt d = o2-o1; T dr = r1-r2, d2 = sq(d), h2 = d2-dr*dr; if (d2 == 0 || h2 < 0) {assert(h2 != 0); return 0;} for (T sign : {-1,1}) { pt v = (d*dr + perp(d)*sqrt(h2)*sign)/d2; out.push_back({o1 + v*r1, o2 + v*r2}); } return 1 + (h2 > 0); } int solve() { int n, m; std::cin >> n >> m; vector<pt> v(n); for (int i = 0; i < n; i++) { std::cin >> v[i]; } while(m--) { int res=-1; pt p; std::cin >> p; for (int i = 0; i < n; i++) { if(segPoint(v[i], v[(i+1)%n], p)<EPS) { res=2; //std::cout << "BOUNDARY" << std::endl; break; } } if(res==2) { std::cout << "BOUNDARY" << std::endl; continue; } cout << (inPolygon(v, p) ? "INSIDE" : "OUTSIDE") << endl; } return 0; } int32_t main() { ios::sync_with_stdio(0); cin.tie(0); int TET = 1; //cin >> TET; for (int i = 1; i <= TET; i++) { #ifdef ONPC cout << "TEST CASE#" << i << endl; #endif if (solve()) { break; } #ifdef ONPC cout << "__________________________" << endl; #endif } #ifdef ONPC cerr << endl << "finished in " << clock() * 1.0 / CLOCKS_PER_SEC << " sec" << endl; #endif }
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 ... Truncated |
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 ... Truncated |
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 |