# 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. }