API tools faq
paste
Advertisement
Guest User

R

a guest
Feb 24th, 2020
718
0
Never
Add comment
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 9.08 KB | None | 0 0
raw download clone embed print report
  1. #include <bits/stdc++.h>
  2.  
  3. using namespace std;
  4.  
  5. typedef double T;
  6. const T INF = 1e100, EPS = 1e-6;
  7. struct PT {
  8.     T x, y;
  9.     PT() {}
  10.     PT(T x, T y) : x(x), y(y) {}
  11.     PT(const PT &p) : x(p.x), y(p.y)        {}
  12.     PT operator + (const PT &p) const {
  13.         return PT(x+p.x, y+p.y);
  14.     } PT operator - (const PT &p)   const {
  15.         return PT(x-p.x, y-p.y);
  16.     } PT operator * (T c) const {
  17.         return PT(x*c,   y*c    );
  18.     } PT operator / (T c) const {
  19.         return PT(x/c,   y/c    );
  20.     } bool operator<(const PT &rhs) const {
  21.         return make_pair(y,x)<make_pair(rhs.y,rhs.x);
  22.     } bool operator==(const PT &rhs) const {
  23.         return abs(y-rhs.y) < EPS and abs(x-rhs.x) < EPS;
  24.     }
  25. };
  26. T dot(PT p, PT q) { return p.x*q.x+p.y*q.y; }
  27. T dist2(PT p, PT q) { return dot(p-q,p-q); }
  28. T cross(PT p,PT q){ return p.x*q.y-p.y*q.x; }
  29. ostream &operator<<(ostream &os, const PT &p) {
  30.     return os << "(" << p.x << "," << p.y << ")";
  31. }
  32. PT RotateCCW90(PT p)     { return PT(-p.y,p.x); }
  33. PT RotateCW90(PT p)     { return PT(p.y,-p.x); }
  34. PT RotateCCW(PT p, T t) {
  35.     return PT(p.x*cos(t)-p.y*sin(t),
  36.         p.x*sin(t)+p.y*cos(t));
  37. }   // rotate a point CCW or CW around the origin
  38. PT ProjectPointLine(PT a, PT b, PT c) {
  39.     return a + (b-a)*dot(c-a, b-a)/dot(b-a, b-a);
  40. }   // project point c onto line through a-b | a!=b
  41. PT ProjectPointSegment(PT a, PT b, PT c) {
  42.     double r = dot(b-a,b-a);
  43.     if(fabs(r) < EPS) return a;
  44.     r = dot(c-a, b-a)/r;
  45.     if(r < 0) return a;
  46.     if(r > 1) return b;
  47.     return a + (b-a)*r;
  48. }   // project pt c onto segment through a & b
  49. bool LinesParallel(PT a, PT b, PT c, PT d) {
  50.     return fabs(cross(b-a, c-d)) < EPS;
  51. }   // line a-b, c-d parallel or collinear
  52. bool LinesCollinear(PT a, PT b, PT c, PT d) {
  53.     return LinesParallel(a, b, c, d)
  54.             && fabs(cross(a-b, a-c)) < EPS
  55.             && fabs(cross(c-d, c-a)) < EPS;
  56. }
  57. bool SegmentsIntersect(PT a, PT b, PT c, PT d) {
  58.     if(LinesCollinear(a, b, c, d)) {
  59.         if(dist2(a, c) < EPS || dist2(a, d) < EPS ||
  60.             dist2(b, c) < EPS || dist2(b, d) < EPS)
  61.             return true;
  62.         if(dot(c-a, c-b) > 0 && dot(d-a, d-b) > 0 &&
  63.             dot(c-b, d-b) > 0) return false;
  64.         return true;
  65.     }
  66.     if(cross(d-a, b-a) * cross(c-a, b-a) > EPS)
  67.         return false;
  68.     if(cross(a-c, d-c) * cross(b-c, d-c) > EPS)
  69.         return false;
  70.     return true;
  71. }   // segment a-b intersect with c-d
  72.  
  73. // Extreme Point for a direction is the farthest
  74. // point in that dir| poly is convex, CCW, no
  75. // redundant points| u direction for extremeness
  76. int extremePoint(const vector<PT> &poly, PT u=PT(0, 1)) {
  77.     int n = (int) poly.size(); int a = 0, b = n;
  78.     while(b - a > 1) {
  79.         int c = (a + b) / 2;
  80.         if(dot(poly[c] - poly[(c+1)%n], u) > 0 and dot(poly[c] - poly[(c-1+n)%n], u) > 0)
  81.             return c;
  82.         T a_dot = dot(poly[(a+1)%n] - poly[a], u);
  83.         T c_dot = dot(poly[(c+1)%n] - poly[c], u);
  84.         // bool a_zer = fabs(a_dot) < EPS;
  85.         // bool c_zer = fabs(c_dot) < EPS;
  86.         bool a_up = !(a_dot < 0);
  87.         bool c_up = !(c_dot < 0);
  88.         bool a_above_c = dot(poly[a]-poly[c], u) > 0;
  89.         // if(a_zer or c_zer) {
  90.         //  if(a_zer and c_zer) {
  91.         //      if(a_above_c) return a;
  92.         //      else return c;
  93.         //  }
  94.         //  else if(a_zer) {
  95.         //      if(c_up) a = c;
  96.         //      else b = c;
  97.         //  }
  98.         //  else {
  99.         //      if(a_up) b = c;
  100.         //      else a = c;
  101.         //  }
  102.         //  continue;
  103.         // }
  104.         if(a_up and !c_up) b = c;
  105.         else if(!a_up and c_up) a = c;
  106.         else if(a_up and c_up) {
  107.             if(a_above_c) b = c;
  108.             else a = c;
  109.         }
  110.         else {
  111.             if(!a_above_c) b = c;
  112.             else a = c;
  113.         }
  114.     }
  115.     if(dot(poly[a] - poly[(a+1)%n], u) > 0 and
  116.         dot(poly[a]-poly[(a-1+n)%n], u) > 0) return a;
  117.     return b % n;
  118. }
  119.  
  120. inline bool OnSegment(PT a, PT b, PT c) {
  121.     return abs(sqrtl(dist2(ProjectPointSegment(a, b, c), c))) < EPS;
  122. }
  123. inline bool SegmentsIntersex(PT a, PT b, PT c, PT d) {
  124.     return OnSegment(a, b, c) or OnSegment(a, b, d) or OnSegment(c, d, a) or OnSegment(c, d, b);
  125. }
  126.  
  127. bool ConvexPolygonIntersect(const vector<PT> &p, const vector<PT> &q) {
  128.     int np = (int) p.size(), nq = (int) q.size();
  129.     if(!np or !nq) return false;
  130.     if(np == 1 and nq == 1) return p.front() == q.front();
  131.     if(np == 1 and nq == 2) return (dist2(p.front(), ProjectPointSegment(q.front(), q.back(), p.front())) < EPS);
  132.     if(np == 2 and nq == 1) return (dist2(q.front(), ProjectPointSegment(p.front(), p.back(), q.front())) < EPS);
  133.     if(np == 2 and nq == 2) return SegmentsIntersect(p.front(), p.back(), q.front(), q.back());
  134.  
  135.     if(np > 1) for(int i=0; i<np; ++i) {
  136.         PT a = p[i], b = p[(i+1) % np];
  137.         // cerr << "P Side: " << a << " - " << b << "\n";
  138.  
  139.         PT dir = b - a;
  140.         PT l_dir = RotateCCW90(dir), r_dir = RotateCW90(dir);
  141.  
  142.         PT plext = p[extremePoint(p, l_dir)];
  143.         PT prext = p[extremePoint(p, r_dir)];
  144.         PT qlext = q[extremePoint(q, l_dir)];
  145.         PT qrext = q[extremePoint(q, r_dir)];
  146.  
  147.         // cerr << "Left extreme in dir " << l_dir << ": " << plext << " " << qlext << "\n";
  148.         // cerr << "Rite extreme in dir " << r_dir << ": " << prext << " " << qrext << "\n";
  149.  
  150.         PT sa = a, sb = a + l_dir * 1;
  151.         PT pl = ProjectPointLine(sa, sb, plext);
  152.         PT pr = ProjectPointLine(sa, sb, prext);
  153.         PT ql = ProjectPointLine(sa, sb, qlext);
  154.         PT qr = ProjectPointLine(sa, sb, qrext);
  155.  
  156.         // cerr << pl << " - " << pr << " | " << ql << " - " << qr << "\n";
  157.         // cerr << "SegmentIntersect: " << SegmentsIntersex(pl, pr, ql, qr) << "\n\n";
  158.         if(!SegmentsIntersex(pl, pr, ql, qr)) return false;
  159.     }
  160.  
  161.     if(nq > 1) for(int i=0; i<nq; ++i) {
  162.         PT a = q[i], b = q[(i+1) % nq];
  163.         // cerr << "Q Side: " << a << " - " << b << "\n";
  164.  
  165.         PT dir = b - a;
  166.         PT l_dir = RotateCCW90(dir), r_dir = RotateCW90(dir);
  167.  
  168.         PT plext = p[extremePoint(p, l_dir)];
  169.         PT prext = p[extremePoint(p, r_dir)];
  170.         PT qlext = q[extremePoint(q, l_dir)];
  171.         PT qrext = q[extremePoint(q, r_dir)];
  172.         // cerr << "Left extreme in dir " << l_dir << ": " << plext << " " << qlext << "\n";
  173.         // cerr << "Rite extreme in dir " << r_dir << ": " << prext << " " << qrext << "\n";
  174.  
  175.         PT sa = a, sb = a + l_dir * 1;
  176.         PT pl = ProjectPointLine(sa, sb, plext);
  177.         PT pr = ProjectPointLine(sa, sb, prext);
  178.         PT ql = ProjectPointLine(sa, sb, qlext);
  179.         PT qr = ProjectPointLine(sa, sb, qrext);
  180.  
  181.         // cerr << pl << " - " << pr << " | " << ql << " - " << qr << "\n";
  182.         // cerr << "SegmentIntersect: " << SegmentsIntersex(pl, pr, ql, qr) << "\n\n";
  183.         if(!SegmentsIntersex(pl, pr, ql, qr)) return false;
  184.     }
  185.  
  186.     return true;
  187. }
  188.  
  189. #define REMOVE_REDUNDANT
  190. T area2(PT a, PT b, PT c) {
  191.     return cross(a,b) + cross(b,c) + cross(c,a);
  192. }
  193. #ifdef REMOVE_REDUNDANT
  194. bool between(const PT &a,const PT &b,const PT &c){
  195.     return (fabs(area2(a,b,c)) < EPS && (a.x-b.x)*
  196.         (c.x-b.x) <= 0 && (a.y-b.y)*(c.y-b.y) <= 0);
  197. }
  198. #endif
  199. void ConvexHull(vector<PT> &pts) {
  200.     sort(pts.begin(), pts.end());
  201.     pts.erase(unique(pts.begin(), pts.end()),
  202.         pts.end());
  203.     vector<PT> up, dn;
  204.     for (int i = 0; i < pts.size(); i++) {
  205.         while (up.size() > 1 && area2(up[up.size()-2],
  206.             up.back(), pts[i]) >= 0) up.pop_back();
  207.         while (dn.size() > 1 && area2(dn[dn.size()-2],
  208.             dn.back(), pts[i]) <= 0) dn.pop_back();
  209.         up.push_back(pts[i]); dn.push_back(pts[i]);
  210.     }
  211.     pts = dn;
  212.     for (int i = (int) up.size() - 2; i >= 1; i--)
  213.         pts.push_back(up[i]);
  214. #ifdef REMOVE_REDUNDANT
  215.     if (pts.size() <= 2) return;
  216.     dn.clear();
  217.     dn.push_back(pts[0]);
  218.     dn.push_back(pts[1]);
  219.     for (int i = 2; i < pts.size(); i++) {
  220.         if (between(dn[dn.size()-2], dn[dn.size()-1],
  221.             pts[i])) dn.pop_back();
  222.         dn.push_back(pts[i]);
  223.     }
  224.     if (dn.size() >= 3 &&
  225.         between(dn.back(), dn[0], dn[1])) {
  226.         dn[0] = dn.back(); dn.pop_back();
  227.     }
  228.     pts = dn;
  229. #endif
  230. }
  231.  
  232. const int N = 1e5 + 7;
  233. typedef struct { int x, y, l; } dat;
  234. dat a[N];
  235.  
  236. inline bool ok(int k) {
  237.     vector<PT> p, q;
  238.     for(int i=0; i<k; ++i) {
  239.         if(a[i].l) p.push_back(PT(a[i].x, a[i].y));
  240.         else q.push_back(PT(a[i].x, a[i].y));
  241.     }
  242.  
  243.     ConvexHull(p);
  244.     ConvexHull(q);
  245.  
  246.     return !ConvexPolygonIntersect(p, q);
  247. }
  248.  
  249. int main() {
  250.     ios::sync_with_stdio(false);
  251.     cin.tie(0); cout.tie(0);
  252.  
  253.     int t, tc = 0;
  254.     cin >> t;
  255.  
  256.     while(t--) {
  257.         int n;
  258.         cin >> n;
  259.         for(int i=0; i<n; ++i) cin >> a[i].x >> a[i].y >> a[i].l;
  260.  
  261.         int lo = 0, hi = n;
  262.         while(lo < hi) {
  263.             int mid = (lo + hi + 1) / 2;
  264.             if(ok(mid)) lo = mid;
  265.             else hi = mid - 1;
  266.         }
  267.  
  268.         cout << "Case " << ++tc << ":\n";
  269.         for(int i=0; i<lo; ++i) cout << "YES\n";
  270.         for(int i=lo; i<n; ++i) cout << "NO\n";
  271.     }
  272.  
  273.     return 0;
  274. }
  275.  
  276. void test() {
  277.     // vector<PT> p = { {1, 2}, {2, 0}, {5, 0}, {7, 3}, {5, 5}, {2, 4} };
  278.    
  279.     // for(int i=0; i<(int) p.size(); ++i) {
  280.     //  PT a = p[i], b = p[(i+1) % (int) p.size()];
  281.     //  cerr << "Side: " << a << " - " << b << "\n";
  282.  
  283.     //  PT dir = b - a;
  284.     //  PT l_dir = RotateCCW90(dir);
  285.     //  PT l_ext = p[extremePoint(p, l_dir)];
  286.     //  cerr << "Left extreme in dir " << l_dir << ": " << l_ext << "\n";
  287.  
  288.     //  PT r_dir = RotateCW90(dir);
  289.     //  PT r_ext = p[extremePoint(p, r_dir)];
  290.     //  cerr << "Right extreme in dir " << r_dir << ": " << r_ext << "\n";
  291.  
  292.     //  cerr << "\n";
  293.     // }
  294.  
  295.     // vector<PT> p = { {1, 2}, {2, 0}, {5, 0}, {7, 3}, {5, 5}, {2, 4} };
  296.     // vector<PT> q = { {8, -4}, {9, 1}, {10, 4}, {7, 6} };
  297.     // vector<PT> q = { {3, 1}, {5, 1}, {6, 3}, {4, 4}, {3, 3} };
  298.     // vector<PT> q = { {1, 4}, {1, 2.000001} };
  299.     // vector<PT> q = { {1, 1.995} };
  300.     // cerr << "Convex Polygon Intersect: " << boolalpha << ConvexPolygonIntersect(p, q) << "\n";
  301. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement
Public Pastes
Advertisement
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy.  OK, I Understand
Not a member of Pastebin yet?
Sign Up, it unlocks many cool features!