Advertisement
cosenza987

asdasdasds

Mar 5th, 2022
1,262
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 14.30 KB | None | 0 0
  1. //Слава Україні, Героям слава 🇺🇦
  2.  
  3. #include <bits/stdc++.h>
  4.  
  5. using namespace std;
  6.  
  7. #define nd second
  8. #define st first
  9.  
  10. typedef long long ll;
  11. typedef long double ld;
  12.  
  13. const ld EPS = 1e-9, PI = acos(-1.);
  14. const ll LINF = 0x3f3f3f3f3f3f3f3f;
  15. const int INF = 0x3f3f3f3f, MOD = 1e9+7;
  16. const int N = 1e5+5;
  17.  
  18. typedef long double type;
  19. typedef pair<int, int> pii;
  20. //for big coordinates change to long long
  21.  
  22. bool ge(type x, type y) { return x + EPS > y; }
  23. bool le(type x, type y) { return x - EPS < y; }
  24. bool eq(type x, type y) { return ge(x, y) and le(x, y); }
  25.  
  26. struct point {
  27.     type x, y;
  28.  
  29.     point() : x(0), y(0) {}
  30.     point(type x, type y) : x(x), y(y) {}
  31.  
  32.     point operator -() { return point(-x, -y); }
  33.     point operator +(point p) { return point(x + p.x, y + p.y); }
  34.     point operator -(point p) { return point(x - p.x, y - p.y); }
  35.  
  36.     point operator *(type k) { return point(k*x, k*y); }
  37.     point operator /(type k) { return point(x/k, y/k); }
  38.  
  39.     //inner product
  40.     type operator *(point p) { return x*p.x + y*p.y; }
  41.     //cross product
  42.     type operator %(point p) { return x*p.y - y*p.x; }
  43.  
  44.     bool operator ==(const point &p) const{ return x == p.x and y == p.y; }
  45.     bool operator !=(const point &p) const{ return x != p.x  or y != p.y; }
  46.     bool operator <(const point &p) const { return (x < p.x) or (x == p.x and y < p.y); }
  47.  
  48.     // 0 => same direction
  49.     // 1 => p is on the left
  50.     //-1 => p is on the right    
  51.     int dir(point o, point p) {
  52.         type x = (*this - o) % (p - o);
  53.         return ge(x,0) - le(x,0);
  54.     }
  55.  
  56.     bool on_seg(point p, point q) {
  57.         if (this->dir(p, q)) return 0;
  58.         return ge(x, min(p.x, q.x)) and le(x, max(p.x, q.x)) and ge(y, min(p.y, q.y)) and le(y, max(p.y, q.y));
  59.     }
  60.  
  61.     ld abs() { return sqrt(x*x + y*y); }
  62.     type abs2() { return x*x + y*y; }
  63.     ld dist(point q) { return (*this - q).abs(); }
  64.     type dist2(point q) { return (*this - q).abs2(); }
  65.  
  66.     ld arg() { return atan2l(y, x); }
  67.  
  68.     // Project point on vector y
  69.     point project(point y) { return y * ((*this * y) / (y * y)); }
  70.  
  71.     // Project point on line generated by points x and y
  72.     point project(point x, point y) { return x + (*this - x).project(y-x); }
  73.  
  74.     ld dist_line(point x, point y) { return dist(project(x, y)); }
  75.  
  76.     ld dist_seg(point x, point y) {
  77.         return project(x, y).on_seg(x, y) ? dist_line(x, y) :  min(dist(x), dist(y));
  78.     }
  79.  
  80.     point rotate(ld sin, ld cos) { return point(cos*x - sin*y, sin*x + cos*y); }
  81.     point rotate(ld a) { return rotate(sin(a), cos(a)); }
  82.  
  83.     // rotate around the argument of vector p
  84.     point rotate(point p) { return rotate(p.x / p.abs(), p.y / p.abs()); }
  85.  
  86. };
  87.  
  88. int direction(point o, point p, point q) { return p.dir(o, q); }
  89.  
  90. point rotate_ccw90(point p)   { return point(-p.y,p.x); }
  91. point rotate_cw90(point p)    { return point(p.y,-p.x); }
  92.  
  93. //for reading purposes avoid using * and % operators, use the functions below:
  94. type dot(point p, point q)     { return p.x*q.x + p.y*q.y; }
  95. type cross(point p, point q)   { return p.x*q.y - p.y*q.x; }
  96.  
  97. //double area
  98. type area_2(point a, point b, point c) { return cross(a,b) + cross(b,c) + cross(c,a); }
  99.  
  100. int angle_less(const point& a1, const point& b1, const point& a2, const point& b2) {
  101.     //angle between (a1 and b1) vs angle between (a2 and b2)
  102.     //1  : bigger
  103.     //-1 : smaller
  104.     //0  : equal
  105.     point p1(dot(   a1, b1), abs(cross(   a1, b1)));
  106.     point p2(dot(   a2, b2), abs(cross(   a2, b2)));
  107.     if(cross(p1, p2) < 0) return 1;
  108.     if(cross(p1, p2) > 0) return -1;
  109.     return 0;
  110. }
  111.  
  112. ostream &operator<<(ostream &os, const point &p) {
  113.     os << "(" << p.x << "," << p.y << ")";
  114.     return os;
  115. }
  116.  
  117. point origin;
  118.  
  119. int above(point p){
  120.     if(p.y == origin.y) return p.x > origin.x;
  121.     return p.y > origin.y;
  122. }
  123.  
  124. bool cmp(point p, point q){
  125.     int tmp = above(q) - above(p);
  126.     if(tmp) return tmp > 0;
  127.     return p.dir(origin,q) > 0;
  128.     //Be Careful: p.dir(origin,q) == 0
  129. }
  130.  
  131. vector<point> graham_hull(vector<point> pts) {
  132.     vector<point> ch(pts.size());
  133.     point mn = pts[0];
  134.     for(point p : pts) if (p.y < mn.y or (p.y == mn.y and p.x < mn.x)) mn = p;
  135.     origin = mn;
  136.     sort(pts.begin(), pts.end(), cmp);
  137.     int n = 0;
  138.     for(point p : pts) {
  139.         while (n > 1 and ch[n-1].dir(ch[n-2], p) < 0) n--;
  140.         ch[n++] = p;
  141.     }
  142.     ch.resize(n);
  143.     return ch;
  144. }
  145.  
  146. ll compute_signed_area(const vector<point> &p) {
  147.     ll area = 0;
  148.     for(int i = 0; i < p.size(); i++) {
  149.         int j = (i+1) % p.size();
  150.         area += p[i].x*p[j].y - p[j].x*p[i].y;
  151.     }
  152.     return area;
  153. }
  154.  
  155. ll compute_area(const vector<point> &p) {
  156.     return abs(compute_signed_area(p));
  157. }
  158.  
  159. ll f(point a, point b, point c) {
  160.     return abs((long long)((a.x - c.x) * (b.y - c.y) - (b.x - c.x) * (a.y - c.y)));
  161. }
  162.  
  163. #define REMOVE_REDUNDANT
  164. #ifdef REMOVE_REDUNDANT
  165. bool between(const point &a, const point &b, const point &c) {
  166.     return (fabs(area_2(a,b,c)) < EPS && (a.x-b.x)*(c.x-b.x) <= 0 && (a.y-b.y)*(c.y-b.y) <= 0);
  167. }
  168. #endif
  169.  
  170. void monotone_hull(vector<point> &pts) {
  171.     sort(pts.begin(), pts.end());
  172.     pts.erase(unique(pts.begin(), pts.end()), pts.end());
  173.     vector<point> up, dn;
  174.     for (int i = 0; i < pts.size(); i++) {
  175.         while (up.size() > 1 && area_2(up[up.size()-2], up.back(), pts[i]) >= 0) up.pop_back();
  176.         while (dn.size() > 1 && area_2(dn[dn.size()-2], dn.back(), pts[i]) <= 0) dn.pop_back();
  177.         up.push_back(pts[i]);
  178.         dn.push_back(pts[i]);
  179.     }
  180.     pts = dn;
  181.     for (int i = (int) up.size() - 2; i >= 1; i--) pts.push_back(up[i]);
  182.  
  183.     #ifdef REMOVE_REDUNDANT
  184.     if (pts.size() <= 2) return;
  185.     dn.clear();
  186.     dn.push_back(pts[0]);
  187.     dn.push_back(pts[1]);
  188.     for (int i = 2; i < pts.size(); i++) {
  189.         if (between(dn[dn.size()-2], dn[dn.size()-1], pts[i])) dn.pop_back();
  190.         dn.push_back(pts[i]);
  191.     }
  192.     if (dn.size() >= 3 && between(dn.back(), dn[0], dn[1])) {
  193.         dn[0] = dn.back();
  194.         dn.pop_back();
  195.     }
  196.     pts = dn;
  197.     #endif
  198. }
  199.  
  200. point project_point_line(point c, point a, point b) {
  201.     ld r = dot(b - a,b - a);
  202.     if (fabs(r) < EPS) return a;
  203.     return a + (b - a)*dot(c - a, b - a)/dot(b - a, b - a);
  204. }
  205.  
  206. point project_point_ray(point c, point a, point b) {
  207.     ld r = dot(b - a, b - a);
  208.     if (fabs(r) < EPS) return a;
  209.     r = dot(c - a, b - a) / r;
  210.     if (le(r, 0)) return a;
  211.     return a + (b - a)*r;
  212. }
  213.  
  214. point project_point_segment(point c, point a, point b) {
  215.     ld r = dot(b - a, b - a);
  216.     if (fabs(r) < EPS) return a;
  217.     r = dot(c - a, b - a)/r;
  218.     if (le(r, 0)) return a;
  219.     if (ge(r, 1)) return b;
  220.     return a + (b - a)*r;
  221. }
  222.  
  223. ld distance_point_line(point c, point a, point b) {
  224.     return c.dist2(project_point_line(c, a, b));
  225. }
  226.  
  227. ld distance_point_ray(point c, point a, point b) {
  228.     return c.dist2(project_point_ray(c, a, b));
  229. }
  230.  
  231. ld distance_point_segment(point c, point a, point b) {
  232.     return c.dist2(project_point_segment(c, a, b));
  233. }
  234.  
  235. //not tested
  236. ld distance_point_plane(ld x, ld y, ld z,
  237.                         ld a, ld b, ld c, ld d)
  238. {
  239.     return fabs(a*x + b*y + c*z - d)/sqrt(a*a + b*b + c*c);
  240. }
  241.  
  242. bool lines_parallel(point a, point b, point c, point d) {
  243.     return fabs(cross(b - a, d - c)) < EPS;
  244. }
  245.  
  246. bool lines_collinear(point a, point b, point c, point d) {
  247.   return lines_parallel(a, b, c, d)
  248.       && fabs(cross(a-b, a-c)) < EPS
  249.       && fabs(cross(c-d, c-a)) < EPS;
  250. }
  251.  
  252. point lines_intersect(point p, point q, point a, point b) {
  253.     point r = q - p, s = b - a, c(p%q, a%b);
  254.     if (eq(r%s,0)) return point(LINF, LINF);
  255.     return point(point(r.x, s.x) % c, point(r.y, s.y) % c) / (r%s);
  256. }
  257.  
  258. //be careful: test LineLineIntersection before using this function
  259. point compute_line_intersection(point a, point b, point c, point d) {
  260.     b = b - a; d = c - d; c = c - a;
  261.     assert(dot(b, b) > EPS && dot(d, d) > EPS);
  262.     return a + b*cross(c, d)/cross(b, d);
  263. }
  264.  
  265. bool line_line_intersect(point a, point b, point c, point d) {
  266.     if(!lines_parallel(a, b, c, d)) return true;
  267.     if(lines_collinear(a, b, c, d)) return true;
  268.     return false;
  269. }
  270.  
  271.  
  272. //rays in direction a -> b, c -> d
  273. bool ray_ray_intersect(point a, point b, point c, point d){
  274.     if (a.dist2(c) < EPS || a.dist2(d) < EPS ||
  275.         b.dist2(c) < EPS || b.dist2(d) < EPS) return true;
  276.     if (lines_collinear(a, b, c, d)) {
  277.         if(ge(dot(b - a, d - c), 0)) return true;
  278.         if(ge(dot(a - c, d - c), 0)) return true;
  279.         return false;
  280.     }
  281.     if(!line_line_intersect(a, b, c, d)) return false;
  282.     point inters = lines_intersect(a, b, c, d);
  283.     if(ge(dot(inters - c, d - c), 0) && ge(dot(inters - a, b - a), 0)) return true;
  284.     return false;
  285. }
  286.  
  287. bool segment_segment_intersect(point a, point b, point c, point d) {
  288.     if (a.dist2(c) < EPS || a.dist2(d) < EPS ||
  289.         b.dist2(c) < EPS || b.dist2(d) < EPS) return true;
  290.     int d1, d2, d3, d4;
  291.     d1 = direction(a, b, c);
  292.     d2 = direction(a, b, d);
  293.     d3 = direction(c, d, a);
  294.     d4 = direction(c, d, b);
  295.     if (d1*d2 < 0 and d3*d4 < 0) return 1;
  296.     return a.on_seg(c, d) or b.on_seg(c, d) or
  297.             c.on_seg(a, b) or d.on_seg(a, b);
  298. }
  299.  
  300. bool segment_line_intersect(point a, point b, point c, point d){
  301.     if(!line_line_intersect(a, b, c, d)) return false;
  302.     point inters = lines_intersect(a, b, c, d);
  303.     if(inters.on_seg(a, b)) return true;
  304.     return false;
  305. }
  306.  
  307. //ray in direction c -> d
  308. bool segment_ray_intersect(point a, point b, point c, point d){
  309.     if (a.dist2(c) < EPS || a.dist2(d) < EPS ||
  310.         b.dist2(c) < EPS || b.dist2(d) < EPS) return true;
  311.     if (lines_collinear(a, b, c, d)) {
  312.         if(c.on_seg(a, b)) return true;
  313.         if(ge(dot(d - c, a - c), 0)) return true;
  314.         return false;
  315.     }
  316.     if(!line_line_intersect(a, b, c, d)) return false;
  317.     point inters = lines_intersect(a, b, c, d);
  318.     if(!inters.on_seg(a, b)) return false;
  319.     if(ge(dot(inters - c, d - c), 0)) return true;
  320.     return false;
  321. }
  322.  
  323. //ray in direction a -> b
  324. bool ray_line_intersect(point a, point b, point c, point d){
  325.     if (a.dist2(c) < EPS || a.dist2(d) < EPS ||
  326.         b.dist2(c) < EPS || b.dist2(d) < EPS) return true;
  327.     if (!line_line_intersect(a, b, c, d)) return false;
  328.     point inters = lines_intersect(a, b, c, d);
  329.     if(!line_line_intersect(a, b, c, d)) return false;
  330.     if(ge(dot(inters - a, b - a), 0)) return true;
  331.     return false;
  332. }
  333.  
  334. ld distance_segment_line(point a, point b, point c, point d){
  335.     if(segment_line_intersect(a, b, c, d)) return 0;
  336.     return min(distance_point_line(a, c, d), distance_point_line(b, c, d));
  337. }
  338.  
  339. ld distance_segment_ray(point a, point b, point c, point d){
  340.     if(segment_ray_intersect(a, b, c, d)) return 0;
  341.     ld min1 = distance_point_segment(c, a, b);
  342.     ld min2 = min(distance_point_ray(a, c, d), distance_point_ray(b, c, d));
  343.     return min(min1, min2);
  344. }
  345.  
  346. ld distance_segment_segment(point a, point b, point c, point d){
  347.     if(segment_segment_intersect(a, b, c, d)) return 0;
  348.     ld min1 = min(distance_point_segment(c, a, b), distance_point_segment(d, a, b));
  349.     ld min2 = min(distance_point_segment(a, c, d), distance_point_segment(b, c, d));
  350.     return min(min1, min2);
  351. }
  352.  
  353. ld DistanceRayLine(point a, point b, point c, point d){
  354.     if(ray_line_intersect(a, b, c, d)) return 0;
  355.     ld min1 = distance_point_line(a, c, d);
  356.     return min1;
  357. }
  358.  
  359. ld DistanceRayRay(point a, point b, point c, point d){
  360.     if(ray_ray_intersect(a, b, c, d)) return 0;
  361.     ld min1 = min(distance_point_ray(c, a, b), distance_point_ray(a, c, d));
  362.     return min1;
  363. }
  364.  
  365. ld DistanceLineLine(point a, point b, point c, point d){
  366.     if(line_line_intersect(a, b, c, d)) return 0;
  367.     return distance_point_line(a, c, d);
  368. }
  369.  
  370. struct edge{
  371.     point ini, fim;
  372.     edge(point ini = point(0,0), point fim = point(0,0)) : ini(ini), fim(fim) {}
  373. };
  374.  
  375. //< here means the edge on the top will be at the begin
  376. bool operator < (const edge& a, const edge& b) {
  377.     if (a.ini == b.ini) return direction(a.ini, a.fim, b.fim) < 0;
  378.     if (a.ini.x < b.ini.x) return direction(a.ini, a.fim, b.ini) < 0;
  379.     return direction(a.ini, b.fim, b.ini) < 0;
  380. }
  381.  
  382. inline bool adj(int a, int b, int n) {return (b == (a + 1)%n or a == (b + 1)%n);}
  383.  
  384. bool is_simple_polygon(const vector<point> &pts){
  385.     vector <pair<point, pii>> eve;
  386.     vector <pair<edge, int>> edgs;
  387.     set <pair<edge, int>> sweep;
  388.     int n = (int)pts.size();
  389.     for(int i = 0; i < n; i++){
  390.         point l = min(pts[i], pts[(i + 1)%n]);
  391.         point r = max(pts[i], pts[(i + 1)%n]);
  392.         eve.push_back({l, {0, i}});
  393.         eve.push_back({r, {1, i}});
  394.         edgs.push_back(make_pair(edge(l, r), i));
  395.     }
  396.     sort(eve.begin(), eve.end());
  397.     for(auto e : eve){
  398.         if(!e.second.first){
  399.             auto cur = sweep.lower_bound(edgs[e.second.second]);
  400.             pair<edge, int> above, below;
  401.             if(cur != sweep.end()){
  402.                 below = *cur;
  403.                 if(!adj(below.nd, e.nd.nd, n) and segment_segment_intersect(pts[below.nd], pts[(below.nd + 1)%n], pts[e.nd.nd], pts[(e.nd.nd + 1)%n]))
  404.                     return false;
  405.             }
  406.             if(cur != sweep.begin()){
  407.                 above = *(--cur);
  408.                 if(!adj(above.nd, e.nd.nd, n) and segment_segment_intersect(pts[above.nd], pts[(above.nd + 1)%n], pts[e.nd.nd], pts[(e.nd.nd + 1)%n]))
  409.                     return false;
  410.             }
  411.             sweep.insert(edgs[e.nd.nd]);
  412.         }
  413.         else{
  414.             auto below = sweep.upper_bound(edgs[e.nd.nd]);
  415.             auto cur = below, above = --cur;
  416.             if(below != sweep.end() and above != sweep.begin()){
  417.                 --above;
  418.                 if(!adj(below->nd, above->nd, n) and segment_segment_intersect(pts[below->nd], pts[(below->nd + 1)%n], pts[above->nd], pts[(above->nd + 1)%n]))
  419.                     return false;
  420.             }
  421.             sweep.erase(cur);
  422.         }
  423.     }
  424.     return true;
  425. }
  426.  
  427. int main() {
  428.     ios_base::sync_with_stdio(false);
  429.     cin.tie(0);
  430.     int n;
  431.     while(cin >> n) {
  432.         if(!n) {
  433.             break;
  434.         }
  435.         vector<point> v(n);
  436.         for(int i = 0; i < n; i++) {
  437.             cin >> v[i].x >> v[i].y;
  438.         }
  439.         if(is_simple_polygon(v)) {
  440.             cout << "YES\n";
  441.         } else {
  442.             cout << "NO\n";
  443.         }
  444.     }
  445.     return 0;
  446. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement