Advertisement
dmkozyrev

Untitled

Jun 24th, 2018
122
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 0.96 KB | None | 0 0
  1. #include <stdio.h>
  2. #include <vector>
  3. #include <algorithm>
  4. #include <cmath>
  5.  
  6. typedef long double ld;
  7.  
  8. struct Point {
  9.     int x, y;
  10.    
  11.     int norm2() const {
  12.         return x*x+y*y;
  13.     }
  14. };
  15.  
  16. int cross(Point a, Point b) {
  17.     return a.x * b.y - a.y * b.x;
  18. }
  19.  
  20. int main() {
  21. //  freopen("input.txt", "rt", stdin);
  22.     int side, n;
  23.     scanf("%d %d", &side, &n);
  24.    
  25.     std::vector<Point> p;
  26.     for (int i = 0; i < n; ++i) {
  27.         int x, y;
  28.         scanf("%d %d", &x, &y);
  29.         x = 2*x-side;
  30.         y = 2*y-side;
  31.         p.push_back(Point{x, y});
  32.         if (x == 0 && y == 0) {
  33.             printf("NO");
  34.             return 0;
  35.         }
  36.     }
  37.     if (n == 1) {
  38.         printf("YES");
  39.         return 0;
  40.     }
  41.     std::sort(p.begin(), p.end(), [](const Point& a, const Point& b){
  42.         ld angle1 = std::atan2(ld(a.y), ld(a.x));
  43.         ld angle2 = std::atan2(ld(b.y), ld(b.x));
  44.         return angle1 < angle2 || (angle1 == angle2 && a.norm2() < b.norm2());
  45.     });
  46.     p.push_back(p[0]);
  47.     for (int i = 1; i <= n; ++i) {
  48.         if (cross(p[i-1], p[i]) < 0) {
  49.             printf("YES");
  50.             return 0;
  51.         }
  52.     }
  53.     printf("NO");
  54.     return 0;
  55. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement