fork download
  1. #include<bits/stdc++.h>
  2. #define file "point_in_polygon"
  3.  
  4. using namespace std;
  5.  
  6. #define int long long
  7. #define pii pair<int,int>
  8. #define pb push_back
  9. #define mp make_pair
  10. #define X first
  11. #define Y second
  12. #define all(x) x.begin(), x.end()
  13. #define sz(x) (int)(x.size())
  14.  
  15. const int NN = 1e3 + 9;
  16.  
  17. struct point {
  18. int x, y;
  19. };
  20.  
  21. int n, m;
  22. point p[NN];
  23.  
  24. int cross(point a, point b, point c) {
  25. point ab={b.x-a.x,b.y-a.y};
  26. point ac={c.x-a.x,c.y-a.y};
  27. return ab.x*ac.y-ab.y*ac.x;
  28. }
  29.  
  30. bool onSegment(point a, point b, point c) {
  31. return cross(a,b,c)==0 &&
  32. min(a.x,c.x)<=b.x && b.x<=max(a.x,c.x) &&
  33. min(a.y,c.y)<=b.y && b.y<=max(a.y,c.y);
  34. }
  35.  
  36. int isInside(point q) {
  37. int dem=0;
  38. for (int i=1;i<=n;i++) {
  39. point a=p[i];
  40. point b=p[i+1];
  41. if (onSegment(a,q,b)) return -1;
  42. if (a.y>b.y) swap(a,b);
  43. if (a.y<q.y && q.y<=b.y && cross(a,b,q)>0)
  44. dem++;
  45. }
  46. return dem%2;
  47. }
  48.  
  49. void process() {
  50. cin>>n>>m;
  51. for (int i=1;i<=n;i++)
  52. cin>>p[i].x>>p[i].y;
  53. p[n+1]=p[1];
  54. for (int i=1;i<=m;i++) {
  55. point q;
  56. cin>>q.x>>q.y;
  57. int res=isInside(q);
  58. if (res==-1) cout<<"BOUNDARY";
  59. else if (res==1) cout<<"INSIDE";
  60. else cout<<"OUTSIDE";
  61. cout<<endl;
  62. }
  63. }
  64.  
  65. signed main() {
  66. cin.tie(0)->sync_with_stdio(0);
  67. // freopen(file".inp","r",stdin);
  68. // freopen(file".out","w",stdout);
  69. int t=1;
  70. // cin>>t;
  71. while (t--) process();
  72. return 0;
  73. }
  74.  
Success #stdin #stdout 0.01s 5292KB
stdin
2 1
3 0
3 4
3 4

stdout
BOUNDARY