Advertisement
Guest User

Untitled

a guest
Dec 5th, 2019
95
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 3.18 KB | None | 0 0
  1. #include <iostream>
  2. #include <vector>
  3. #include <algorithm>
  4.  
  5. using namespace std;
  6.  
  7. enum {LEFT,  RIGHT,  BEYOND,  BEHIND, BETWEEN, ORIGIN, DESTINATION};
  8. class Point {
  9. public:
  10.     int x;
  11.     int y;
  12.  
  13.     Point(int x, int y) : x(x), y(y) {}
  14.  
  15.     Point() {}
  16.  
  17.     Point operator+(Point& p){
  18.         return Point(x + p.x, y + p.y);
  19.     }
  20.  
  21.     __int64_t length()
  22.     {
  23.         return x*x + y*y;
  24.     }
  25.  
  26.     Point operator-(Point &p){
  27.         return Point(x - p.x, y - p.y);
  28.     }
  29.     int operator==(Point &p)
  30.     {
  31.         return (x == p.x) && (y == p.y);
  32.     }
  33.  
  34.     int classify(Point& p0, Point& p1){
  35.         Point p2 = *this;
  36.         Point a = p1 - p0;
  37.         Point b = p2 - p0;
  38.         double sa = a.x * b.y - b.x * a.y;
  39.         if (sa > 0.0)
  40.             return LEFT;
  41.         if (sa < 0.0)
  42.             return RIGHT;
  43.         if ((a.x * b.x < 0.0) || (a.y * b.y < 0.0))
  44.             return BEHIND;
  45.         if (a.length() < b.length())
  46.             return BEYOND;
  47.         if (p0 == p2)
  48.             return ORIGIN;
  49.         if (p1 == p2)
  50.             return DESTINATION;
  51.         return BETWEEN;
  52.     }
  53. };
  54.  
  55. bool pointInTriangle(Point p, Point a, Point b, Point c)
  56. {
  57.     return ((p.classify (a, b) != LEFT) &&
  58.             (p.classify(b, c) != LEFT) &&
  59.             (p.classify(c, a) != LEFT));
  60. }
  61.  
  62. enum { INSIDE, OUTSIDE, BOUNDARY };
  63. enum { TOUCHING, CROSSING, INESSENTIAL };
  64.  
  65.  
  66. int edgeType (Point &a, Point &v, Point &w)
  67. {
  68.     switch (a.classify(v, w)) {
  69.         case LEFT:
  70.             return ((v.y < a.y) && (a.y <= w.y)) ? CROSSING : INESSENTIAL;
  71.         case RIGHT:
  72.             return ((w.y < a.y) && (a.y <= v.y)) ? CROSSING : INESSENTIAL;
  73.         case BETWEEN:
  74.         case ORIGIN:
  75.         case DESTINATION:
  76.             return TOUCHING;
  77.         default:
  78.             return INESSENTIAL;
  79.     }
  80. }
  81.  
  82.  
  83. int pointInPolygon(Point &a, vector<Point> &p)
  84. {
  85.     int parity = 0;
  86.     for (int i = 0;  i < p.size(); i++) {
  87.         int next = i + 1;
  88.         if (i + 1 == p.size()) {
  89.             next = 0;
  90.         }
  91.         switch (edgeType(a, p[i], p[next])) {
  92.             case TOUCHING:
  93.                 return BOUNDARY;
  94.             case CROSSING:
  95.                 parity = 1 - parity;
  96.         }
  97.     }
  98.     return (parity ? INSIDE : OUTSIDE);
  99. }
  100.  
  101. inline __int64_t sign (const Point& p1, const Point& p2, const Point& p3)
  102. {
  103.     return ((__int64_t) p1.x - p3.x) * (p2.y - p3.y) - ((__int64_t) p2.x - p3.x) * (p1.y - p3.y);
  104. }
  105.  
  106.  
  107. int main() {
  108.     //freopen("inside.in", "r", stdin);
  109.     //freopen("inside.out", "w", stdout);
  110.  
  111.     int n;
  112.     cin >> n;
  113.     int x_q, y_q;
  114.     cin >> x_q >> y_q;
  115.     Point q(x_q, y_q);
  116.  
  117.     vector<Point> p(n);
  118.     for (int i = 0; i < n; ++i) {
  119.         int x, y;
  120.         cin >> x >> y;
  121.         p[i].x = x, p[i].y = y;
  122.     }
  123.     /*
  124.     reverse(p.begin(), p.end());
  125.     bool need_reverse = sign(p[n - 1], p[0], p[1]) < 0;
  126.     if (need_reverse) {
  127.         reverse(p.begin(), p.end());
  128.     }
  129.      */
  130.  
  131.     auto loc = pointInPolygon(q, p);
  132.     if (loc == BOUNDARY) {
  133.         cout << "YES" << endl;
  134.     } else if (loc == INSIDE) {
  135.         cout << "YES" << endl;
  136.     } else if (loc == OUTSIDE) {
  137.         cout << "NO" << endl;
  138.     }
  139. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement