Advertisement
Guest User

Untitled

a guest
Jan 29th, 2020
95
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.82 KB | None | 0 0
  1. //
  2. // Created by Елена on 07.01.2020.
  3. //
  4. #include <iostream>
  5. #include <vector>
  6. #include <algorithm>
  7. //#include <ostream>
  8.  
  9. using namespace std;
  10.  
  11. struct point {
  12.     int x, y;
  13.  
  14.     point() {}
  15.  
  16.     point(int x, int y) : x(x), y(y) {}
  17.  
  18.     bool operator==(const point &rhs) const {
  19.         return x == rhs.x && y == rhs.y;
  20.     }
  21. };
  22.  
  23. int rotate_det(const point &a, const point &b, const point &c) {
  24.     return (b.x - a.x) * (c.y - a.y) - (c.x - a.x) * (b.y - a.y);
  25. }
  26.  
  27. bool left_turn(const point &a, const point &b, const point &c) {
  28.     return rotate_det(a, b, c) > 0;
  29. }
  30.  
  31. int main() {
  32.     int n, x0 ,y0;
  33.     cin >> n >> x0 >> y0;
  34.     vector<point> polygon;
  35.     for (int i = 0; i < n; i++) {
  36.         int x, y;
  37.         cin >> x >> y;
  38.         polygon.emplace_back(x, y);
  39.     }
  40.     if (left_turn(polygon[polygon.size() - 1 - 2], polygon[polygon.size() - 1 - 1], polygon[polygon.size() - 1])
  41.     || left_turn(polygon[0], polygon[1], polygon[2])) {
  42.         reverse(polygon.begin(), polygon.end());
  43.     }
  44.  
  45.     point p(x0, y0);
  46.     int count = 0;
  47.     bool flag = false;
  48.     for (size_t i = 0; i < polygon.size(); i++) {
  49.         point l = polygon[i];
  50.         point r;
  51.         if(i == polygon.size() - 1) {
  52.             r = polygon[0];
  53.         } else {
  54.             r = polygon[i + 1];
  55.         }
  56.         if (l.y > r.y) {
  57.             swap(l, r);
  58.         }
  59.         if (r.y < p.y || l.y >= p.y) continue;
  60.         int orient = rotate_det(l, r, p);
  61.         if (orient == 0) {
  62.             flag = true;
  63.             break;
  64.         }
  65.         if (orient > 0) {
  66.             count++;
  67.         }
  68.     }
  69.     if(count % 2 ) {
  70.         flag = true;
  71.     }
  72.     if(flag) {
  73.         cout << "YES" << endl;
  74.     } else {
  75.         cout << "NO" << endl;
  76.     }
  77. }
  78. /*
  79.  9 5 2
  80.  0 2
  81.  3 0
  82.  2 2
  83.  6 1
  84.  5 6
  85.  4 4
  86.  3 5
  87.  3 3
  88.  1 3
  89.  
  90.  */
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement