Advertisement
Merevoli

2D (Polygon)

Dec 4th, 2021
498
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. typedef vector < Point > Polygon;
  2. double area2(Point a, Point b, Point c) {
  3.     return a % b + b % c + c % a;
  4. }
  5. #ifdef REMOVE_REDUNDANT
  6. bool between(const Point & a,
  7.     const Point & b,
  8.         const Point & c) {
  9.     return (fabs(area2(a, b, c)) < EPS && (a.x - b.x) * (c.x - b.x) <= 0 && (a.y - b.y) * (c.y - b.y) <= 0);
  10. }
  11. #endif
  12. void ConvexHull(Polygon & pts) {
  13.     sort(pts.begin(), pts.end());
  14.     pts.erase(unique(pts.begin(), pts.end()), pts.end());
  15.     Polygon up, dn;
  16.     for (int i = 0; i < pts.size(); i++) {
  17.         while (up.size() > 1 && area2(up[up.size() - 2], up.back(), pts[i]) >= 0)
  18.             up.pop_back();
  19.         while (dn.size() > 1 && area2(dn[dn.size() - 2], dn.back(), pts[i]) <= 0)
  20.             dn.pop_back();
  21.         up.push_back(pts[i]);
  22.         dn.push_back(pts[i]);
  23.     }
  24.     pts = dn;
  25.     for (int i = (int) up.size() - 2; i >= 1; i--) pts.push_back(up[i]);
  26.     #ifdef REMOVE_REDUNDANT
  27.     if (pts.size() <= 2) return;
  28.     dn.clear();
  29.     dn.push_back(pts[0]);
  30.     dn.push_back(pts[1]);
  31.     for (int i = 2; i < pts.size(); i++) {
  32.         if (between(dn[dn.size() - 2], dn[dn.size() - 1], pts[i])) dn.pop_back();
  33.         dn.push_back(pts[i]);
  34.     }
  35.     if (dn.size() >= 3 && between(dn.back(), dn[0], dn[1])) {
  36.         dn[0] = dn.back();
  37.         dn.pop_back();
  38.     }
  39.     pts = dn;
  40.     #endif
  41. }
  42. Polygon convex_hull(Polygon P) {
  43.     Polygon tmp = P;
  44.     ConvexHull(tmp);
  45.     return tmp;
  46. }
  47. double signed_area(Polygon p) {
  48.     double area = 0;
  49.     for (int i = 0; i < p.size(); i++) {
  50.         int j = (i + 1) % p.size();
  51.         area += p[i].x * p[j].y - p[j].x * p[i].y;
  52.     }
  53.     return area / 2.0;
  54. }
  55. double area(const Polygon & p) {
  56.     return fabs(signed_area(p));
  57. }
  58. Point centroid(Polygon p) {
  59.     Point c(0, 0);
  60.     double scale = 6.0 * signed_area(p);
  61.     for (int i = 0; i < p.size(); i++) {
  62.         int j = (i + 1) % p.size();
  63.         c = c + (p[i] + p[j]) * (p[i].x * p[j].y - p[j].x * p[i].y);
  64.     }
  65.     return c / scale;
  66. }
  67. double perimeter(Polygon P) {
  68.     double res = 0;
  69.     for (int i = 0; i < P.size(); ++i) {
  70.         int j = (i + 1) % P.size();
  71.         res += (P[i] - P[j]).len();
  72.     }
  73.     return res;
  74. }
  75. bool is_convex(const Polygon & P) {
  76.     int sz = (int) P.size();
  77.     if (sz <= 2) return false;
  78.     int isLeft = ccw(P[0], P[1], P[2]);
  79.     for (int i = 1; i < sz; i++)
  80.         if (ccw(P[i], P[(i + 1) % sz], P[(i + 2) % sz]) * isLeft < 0) return false;
  81.     return true;
  82. }
  83. bool in_polygon(const Polygon & p, Point q) {
  84.     if ((int) p.size() == 0) return false;
  85.     int n = (int) p.size();
  86.     for (int i = 0; i < n; i++) {
  87.         int j = (i + 1) % n;
  88.         Point u = p[i], v = p[j];
  89.         if (u > v) swap(u, v);
  90.         if (ccw(u, v, q) == 0 && u <= q && q <= v) return true;
  91.     }
  92.     int c = 0;
  93.     for (int i = 0; i < n; i++) {
  94.         int j = (i + 1) % n;
  95.         if ((p[i].y <= q.y && q.y < p[j].y || p[j].y <= q.y && q.y < p[i].y) &&
  96.             q.x < p[i].x + (p[j].x - p[i].x) * (q.y - p[i].y) / (p[j].y - p[i].y)) c = !c;
  97.     }
  98.     return c;
  99. }
  100. #define Det(a, b, c)\
  101.     ((double)(b.x - a.x) * (double)(c.y - a.y)\ -
  102.         (double)(b.y - a.y) * (double)(c.x - a.x))
  103. bool in_convex(Polygon & l, Point p) {
  104.     int a = 1, b = l.size() - 1, c;
  105.     if (Det(l[0], l[a], l[b]) > 0) swap(a, b);
  106.     if (Det(l[0], l[a], p) >= 0 || Det(l[0], l[b], p) <= 0) return false;
  107.     while (abs(a - b) > 1) {
  108.         c = (a + b) / 2;
  109.         if (Det(l[0], l[c], p) > 0) b = c;
  110.         else a = c;
  111.     }
  112.     return Det(l[a], l[b], p) < 0;
  113. }
  114. Polygon polygon_cut(const Polygon & P, Line l) {
  115.     Polygon Q;
  116.     for (int i = 0; i < P.size(); ++i) {
  117.         Point A = P[i], B = (i == P.size() - 1) ? P[0] : P[i + 1];
  118.         if (ccw(l.A, l.B, A) != -1) Q.push_back(A);
  119.         if (ccw(l.A, l.B, A) * ccw(l.A, l.B, B) < 0) {
  120.             Point p;
  121.             areIntersect(Line(A, B), l, p);
  122.             Q.push_back(p);
  123.         }
  124.     }
  125.     return Q;
  126. }
  127. bool intersect_1pt(Point a, Point b, Point c, Point d, Point & r) {
  128.     double D = (b - a) % (d - c);
  129.     if (cmp(D, 0) == 0) return false;
  130.     double t = ((c - a) % (d - c)) / D;
  131.     double s = -((a - c) % (b - a)) / D;
  132.     r = a + (b - a) * t;
  133.     return cmp(t, 0) >= 0 && cmp(t, 1) <= 0 && cmp(s, 0) >= 0 && cmp(s, 1) <= 0;
  134. }
  135. Polygon convex_intersect(Polygon P, Polygon Q) {
  136.     const int n = P.size(),
  137.         m = Q.size();
  138.     int a = 0, b = 0, aa = 0, ba = 0;
  139.     enum {
  140.         Pin,
  141.         Qin,
  142.         Unknown
  143.     } in = Unknown;
  144.     Polygon R;
  145.     do {
  146.         int a1 = (a + n - 1) % n, b1 = (b + m - 1) % m;
  147.         double C = (P[a] - P[a1]) % (Q[b] - Q[b1]);
  148.         Point r;
  149.         double A = (P[a1] - Q[b]) % (P[a] - Q[b]);
  150.         double B = (Q[b1] - P[a]) % (Q[b] - P[a]);
  151.         if (intersect_1pt(P[a1], P[a], Q[b1], Q[b], r)) {
  152.             if ( in == Unknown) aa = ba = 0;
  153.             R.push_back(r); in = B > 0 ? Pin : A > 0 ? Qin : in ;
  154.         }
  155.         if (C == 0 && B == 0 && A == 0) {
  156.             if ( in == Pin) {
  157.                 b = (b + 1) % m;
  158.                 ++ba;
  159.             } else {
  160.                 a = (a + 1) % m;
  161.                 ++aa;
  162.             }
  163.         } else if (C >= 0) {
  164.             if (A > 0) {
  165.                 if ( in == Pin) R.push_back(P[a]);
  166.                 a = (a + 1) % n;
  167.                 ++aa;
  168.             } else {
  169.                 if ( in == Qin) R.push_back(Q[b]);
  170.                 b = (b + 1) % m;
  171.                 ++ba;
  172.             }
  173.         } else {
  174.             if (B > 0) {
  175.                 if ( in == Qin) R.push_back(Q[b]);
  176.                 b = (b + 1) % m;
  177.                 ++ba;
  178.             } else {
  179.                 if ( in == Pin) R.push_back(P[a]);
  180.                 a = (a + 1) % n;
  181.                 ++aa;
  182.             }
  183.         }
  184.     } while ((aa < n || ba < m) && aa < 2 * n && ba < 2 * m);
  185.     if ( in == Unknown) {
  186.         if (in_convex(Q, P[0])) return P;
  187.         if (in_convex(P, Q[0])) return Q;
  188.     }
  189.     return R;
  190. }
  191. double convex_diameter(Polygon pt) {
  192.     const int n = pt.size();
  193.     int is = 0, js = 0;
  194.     for (int i = 1; i < n; ++i) {
  195.         if (pt[i].y > pt[is].y) is = i;
  196.         if (pt[i].y < pt[js].y) js = i;
  197.     }
  198.     double maxd = (pt[is] - pt[js]).norm();
  199.     int i, maxi, j, maxj;
  200.     i = maxi = is;
  201.     j = maxj = js;
  202.     do {
  203.         int jj = j + 1;
  204.         if (jj == n) jj = 0;
  205.         if ((pt[i] - pt[jj]).norm() > (pt[i] - pt[j]).norm()) j = (j + 1) % n;
  206.         else i = (i + 1) % n;
  207.         if ((pt[i] - pt[j]).norm() > maxd) {
  208.             maxd = (pt[i] - pt[j]).norm();
  209.             maxi = i;
  210.             maxj = j;
  211.         }
  212.     } while (i != is || j != js);
  213.     return maxd; /* farthest pair is (maxi, maxj). */
  214. }
  215. #define MAXN 100
  216. double mindist = 1e20;
  217. Point x, y;
  218. bool cmpy(Point u, Point v) {
  219.     if (u.x == v.x) return u.y < v.y;
  220.     return u.x < v.x;
  221. }
  222. void upd_ans(Point _x, Point _y) {
  223.     x = _x;
  224.     y = _y;
  225. }
  226. void rec(int l, int r, Point a[]) {
  227.     if (r - l <= 3) {
  228.         for (int i = l; i <= r; ++i)
  229.             for (int j = i + 1; j <= r; ++j) upd_ans(a[i], a[j]);
  230.         sort(a + l, a + r + 1, cmpy);
  231.         return;
  232.     }
  233.     int m = (l + r) >> 1;
  234.     int midx = a[m].x;
  235.     rec(l, m, a), rec(m + 1, r, a);
  236.     static Point t[MAXN];
  237.     merge(a + l, a + m + 1, a + m + 1, a + r + 1, t, cmpy);
  238.     copy(t, t + r - l + 1, a + l);
  239.     int tsz = 0;
  240.     for (int i = l; i <= r; ++i)
  241.         if (fabs(a[i].x - midx) < mindist) {
  242.             for (int j = tsz - 1; j >= 0 && a[i].y - t[j].y < mindist; --j) upd_ans(a[i], t[j]);
  243.             t[tsz++] = a[i];
  244.         }
  245. }
  246. bool isSquare(long long x) {
  247.     long long tmp = (long long) sqrt(x);
  248.     return (x == tmp * tmp);
  249. }
  250. bool isIntegerCoordinates(int x, int y, int z) {
  251.     long long s = (long long)(x + y + z) * (x + y - z) * (x + z - y) * (y + z - x);
  252.     return (s % 4 == 0 && isSquare(s / 4));
  253. }
Advertisement
RAW Paste Data Copied
Advertisement