This documentation is automatically generated by online-judge-tools/verification-helper
View the Project on GitHub ngthanhtrung23/ACM_Notebook_new
#define PROBLEM "http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=CGL_4_A" #include "../../template.h" #include "../basic.h" #include "../polygon.h" void solve() { int n; cin >> n; Polygon g(n); for (auto& p : g) cin >> p; ConvexHull(g); int idx = 0; FOR(i,1,n-1) if (cmpy(g[i], g[idx])) idx = i; cout << g.size() << endl; REP(i,g.size()) cout << (fixed) << setprecision(0) << g[(idx + i) % g.size()] << '\n'; }
#line 1 "Geometry/tests/aizu_cgl_4_a_polygon_convex_hull.test.cpp" #define PROBLEM "http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=CGL_4_A" #line 1 "template.h" #include <bits/stdc++.h> using namespace std; #define FOR(i,a,b) for(int i=(a),_b=(b); i<=_b; i++) #define FORD(i,a,b) for(int i=(a),_b=(b); i>=_b; i--) #define REP(i,a) for(int i=0,_a=(a); i<_a; i++) #define EACH(it,a) for(__typeof(a.begin()) it = a.begin(); it != a.end(); ++it) #define DEBUG(x) { cout << #x << " = "; cout << (x) << endl; } #define PR(a,n) { cout << #a << " = "; FOR(_,1,n) cout << a[_] << ' '; cout << endl; } #define PR0(a,n) { cout << #a << " = "; REP(_,n) cout << a[_] << ' '; cout << endl; } #define sqr(x) ((x) * (x)) // For printing pair, container, etc. // Copied from https://quangloc99.github.io/2021/07/30/my-CP-debugging-template.html template<class U, class V> ostream& operator << (ostream& out, const pair<U, V>& p) { return out << '(' << p.first << ", " << p.second << ')'; } template<class Con, class = decltype(begin(declval<Con>()))> typename enable_if<!is_same<Con, string>::value, ostream&>::type operator << (ostream& out, const Con& con) { out << '{'; for (auto beg = con.begin(), it = beg; it != con.end(); it++) { out << (it == beg ? "" : ", ") << *it; } return out << '}'; } template<size_t i, class T> ostream& print_tuple_utils(ostream& out, const T& tup) { if constexpr(i == tuple_size<T>::value) return out << ")"; else return print_tuple_utils<i + 1, T>(out << (i ? ", " : "(") << get<i>(tup), tup); } template<class ...U> ostream& operator << (ostream& out, const tuple<U...>& t) { return print_tuple_utils<0, tuple<U...>>(out, t); } mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count()); long long get_rand(long long r) { return uniform_int_distribution<long long> (0, r-1)(rng); } template<typename T> vector<T> read_vector(int n) { vector<T> res(n); for (int& x : res) cin >> x; return res; } void solve(); int main() { ios::sync_with_stdio(0); cin.tie(0); solve(); return 0; } #line 2 "Geometry/basic.h" // Basic geometry objects: Point, Line, Segment // Works with both integers and floating points // Unless the problem has precision issue, can use Point, which uses double // and has more functionalities. // For integers, can use P<long long> #ifndef EPS // allow test files to overwrite EPS #define EPS 1e-6 #endif const double PI = acos(-1.0l); double DEG_to_RAD(double d) { return d * PI / 180.0; } double RAD_to_DEG(double r) { return r * 180.0 / PI; } inline int cmp(double a, double b) { return (a < b - EPS) ? -1 : ((a > b + EPS) ? 1 : 0); } // for int types template<typename T, typename std::enable_if<!std::is_floating_point<T>::value>::type * = nullptr> inline int cmp(T a, T b) { return (a == b) ? 0 : (a < b) ? -1 : 1; } template<typename T> struct P { T x, y; P() { x = y = T(0); } P(T _x, T _y) : x(_x), y(_y) {} P operator + (const P& a) const { return P(x+a.x, y+a.y); } P operator - (const P& a) const { return P(x-a.x, y-a.y); } P operator * (T k) const { return P(x*k, y*k); } P<double> operator / (double k) const { return P(x/k, y/k); } T operator * (const P& a) const { return x*a.x + y*a.y; } // dot product T operator % (const P& a) const { return x*a.y - y*a.x; } // cross product int cmp(const P<T>& q) const { if (int t = ::cmp(x,q.x)) return t; return ::cmp(y,q.y); } #define Comp(x) bool operator x (const P& q) const { return cmp(q) x 0; } Comp(>) Comp(<) Comp(==) Comp(>=) Comp(<=) Comp(!=) #undef Comp T norm() { return x*x + y*y; } // Note: There are 2 ways for implementing len(): // 1. sqrt(norm()) --> fast, but inaccurate (produce some values that are of order X^2) // 2. hypot(x, y) --> slow, but much more accurate double len() { return hypot(x, y); } P<double> rotate(double alpha) { double cosa = cos(alpha), sina = sin(alpha); return P(x * cosa - y * sina, x * sina + y * cosa); } }; using Point = P<double>; // Compare points by (y, x) template<typename T = double> bool cmpy(const P<T>& a, const P<T>& b) { if (cmp(a.y, b.y)) return a.y < b.y; return a.x < b.x; }; template<typename T> int ccw(P<T> a, P<T> b, P<T> c) { return cmp((b-a)%(c-a), T(0)); } int RE_TRAI = ccw(P<int>(0, 0), P<int>(0, 1), P<int>(-1, 1)); int RE_PHAI = ccw(P<int>(0, 0), P<int>(0, 1), P<int>(1, 1)); template<typename T> istream& operator >> (istream& cin, P<T>& p) { cin >> p.x >> p.y; return cin; } template<typename T> ostream& operator << (ostream& cout, const P<T>& p) { cout << p.x << ' ' << p.y; return cout; } double angle(Point a, Point o, Point b) { // min of directed angle AOB & BOA a = a - o; b = b - o; return acos((a * b) / sqrt(a.norm()) / sqrt(b.norm())); } double directed_angle(Point a, Point o, Point b) { // angle AOB, in range [0, 2*PI) double t = -atan2(a.y - o.y, a.x - o.x) + atan2(b.y - o.y, b.x - o.x); while (t < 0) t += 2*PI; return t; } // Distance from p to Line ab (closest Point --> c) // i.e. c is projection of p on AB double distToLine(Point p, Point a, Point b, Point &c) { Point ap = p - a, ab = b - a; double u = (ap * ab) / ab.norm(); c = a + (ab * u); return (p-c).len(); } // Distance from p to segment ab (closest Point --> c) double distToLineSegment(Point p, Point a, Point b, Point &c) { Point ap = p - a, ab = b - a; double u = (ap * ab) / ab.norm(); if (u < 0.0) { c = Point(a.x, a.y); return (p - a).len(); } if (u > 1.0) { c = Point(b.x, b.y); return (p - b).len(); } return distToLine(p, a, b, c); } // NOTE: WILL NOT WORK WHEN a = b = 0. struct Line { double a, b, c; // ax + by + c = 0 Point A, B; // Added for polygon intersect line. Do not rely on assumption that these are valid Line(double _a, double _b, double _c) : a(_a), b(_b), c(_c) {} Line(Point _A, Point _B) : A(_A), B(_B) { a = B.y - A.y; b = A.x - B.x; c = - (a * A.x + b * A.y); } Line(Point P, double m) { a = -m; b = 1; c = -((a * P.x) + (b * P.y)); } double f(Point p) { return a*p.x + b*p.y + c; } }; ostream& operator << (ostream& cout, const Line& l) { cout << l.a << "*x + " << l.b << "*y + " << l.c; return cout; } bool areParallel(Line l1, Line l2) { return cmp(l1.a*l2.b, l1.b*l2.a) == 0; } bool areSame(Line l1, Line l2) { return areParallel(l1 ,l2) && cmp(l1.c*l2.a, l2.c*l1.a) == 0 && cmp(l1.c*l2.b, l1.b*l2.c) == 0; } bool areIntersect(Line l1, Line l2, Point &p) { if (areParallel(l1, l2)) return false; double dx = l1.b*l2.c - l2.b*l1.c; double dy = l1.c*l2.a - l2.c*l1.a; double d = l1.a*l2.b - l2.a*l1.b; p = Point(dx/d, dy/d); return true; } // closest point from p in line l. void closestPoint(Line l, Point p, Point &ans) { if (fabs(l.b) < EPS) { ans.x = -(l.c) / l.a; ans.y = p.y; return; } if (fabs(l.a) < EPS) { ans.x = p.x; ans.y = -(l.c) / l.b; return; } Line perp(l.b, -l.a, - (l.b*p.x - l.a*p.y)); areIntersect(l, perp, ans); } // Segment intersect // Tested: // - https://cses.fi/problemset/task/2190/ // returns true if p is on segment [a, b] template<typename T> bool onSegment(const P<T>& a, const P<T>& b, const P<T>& p) { return ccw(a, b, p) == 0 && min(a.x, b.x) <= p.x && p.x <= max(a.x, b.x) && min(a.y, b.y) <= p.y && p.y <= max(a.y, b.y); } // Returns true if segment [a, b] and [c, d] intersects // End point also returns true template<typename T> bool segmentIntersect(const P<T>& a, const P<T>& b, const P<T>& c, const P<T>& d) { if (onSegment(a, b, c) || onSegment(a, b, d) || onSegment(c, d, a) || onSegment(c, d, b)) { return true; } return ccw(a, b, c) * ccw(a, b, d) < 0 && ccw(c, d, a) * ccw(c, d, b) < 0; } #line 1 "Geometry/polygon.h" // Polygon: convex hull, in polygon, convex diameter .. // Functions with param vector<P<T>> works with both integers and floating points // Functions with param Polygon works with floating points only. typedef vector< Point > Polygon; // Convex Hull: // If minimum point --> #define REMOVE_REDUNDANT // Known issues: // - Max. point does not work when some points are the same. // Tested: // - (min points) https://open.kattis.com/problems/convexhull // - (max points) https://cses.fi/problemset/task/2195 // #define REMOVE_REDUNDANT template<typename T> T area2(P<T> a, P<T> b, P<T> c) { return a%b + b%c + c%a; } template<typename T> void ConvexHull(vector<P<T>> &pts) { sort(pts.begin(), pts.end()); pts.erase(unique(pts.begin(), pts.end()), pts.end()); vector<P<T>> up, dn; for (int i = 0; i < (int) pts.size(); i++) { #ifdef REMOVE_REDUNDANT while (up.size() > 1 && area2(up[up.size()-2], up.back(), pts[i]) >= 0) up.pop_back(); while (dn.size() > 1 && area2(dn[dn.size()-2], dn.back(), pts[i]) <= 0) dn.pop_back(); #else while (up.size() > 1 && area2(up[up.size()-2], up.back(), pts[i]) > 0) up.pop_back(); while (dn.size() > 1 && area2(dn[dn.size()-2], dn.back(), pts[i]) < 0) dn.pop_back(); #endif up.push_back(pts[i]); dn.push_back(pts[i]); } pts = dn; for (int i = (int) up.size() - 2; i >= 1; i--) pts.push_back(up[i]); #ifdef REMOVE_REDUNDANT if (pts.size() <= 2) return; dn.clear(); dn.push_back(pts[0]); dn.push_back(pts[1]); for (int i = 2; i < (int) pts.size(); i++) { if (onSegment(dn[dn.size()-2], pts[i], dn.back())) dn.pop_back(); dn.push_back(pts[i]); } if (dn.size() >= 3 && onSegment(dn.back(), dn[1], dn[0])) { dn[0] = dn.back(); dn.pop_back(); } pts = dn; #endif } // Area, perimeter, centroid template<typename T> T signed_area2(vector<P<T>> p) { T area(0); for(int i = 0; i < (int) p.size(); i++) { area += p[i] % p[(i + 1) % p.size()]; } return area; } double area(const Polygon &p) { return std::abs(signed_area2(p) / 2.0); } Point centroid(Polygon p) { Point c(0,0); double scale = 3.0 * signed_area2(p); for (int i = 0; i < (int) p.size(); i++){ int j = (i+1) % p.size(); c = c + (p[i]+p[j])*(p[i].x*p[j].y - p[j].x*p[i].y); } return c / scale; } double perimeter(Polygon p) { double res = 0; for(int i = 0; i < (int) p.size(); ++i) { int j = (i + 1) % p.size(); res += (p[i] - p[j]).len(); } return res; } // Is convex: checks if polygon is convex. // Return true for degen points (all vertices are collinear) template<typename T> bool is_convex(const vector<P<T>> &P) { int sz = (int) P.size(); int min_ccw = 2, max_ccw = -2; for (int i = 0; i < sz; i++) { int c = ccw(P[i], P[(i+1) % sz], P[(i+2) % sz]); min_ccw = min(min_ccw, c); max_ccw = max(max_ccw, c); } return min_ccw * max_ccw >= 0; } // Inside polygon: O(N). Works with any polygon // Tested: // - https://open.kattis.com/problems/pointinpolygon // - https://open.kattis.com/problems/cuttingpolygon enum PolygonLocation { OUT, ON, IN }; PolygonLocation in_polygon(const Polygon &p, Point q) { if ((int)p.size() == 0) return PolygonLocation::OUT; // Check if point is on edge. int n = p.size(); REP(i,n) { int j = (i + 1) % n; Point u = p[i], v = p[j]; if (u > v) swap(u, v); if (ccw(u, v, q) == 0 && u <= q && q <= v) return PolygonLocation::ON; } // Check if point is strictly inside. int c = 0; for (int i = 0; i < n; i++) { int j = (i + 1) % n; if (((p[i].y <= q.y && q.y < p[j].y) || (p[j].y <= q.y && q.y < p[i].y)) && q.x < p[i].x + (p[j].x - p[i].x) * (q.y - p[i].y) / (double) (p[j].y - p[i].y)) { c = !c; } } return c ? PolygonLocation::IN : PolygonLocation::OUT; } // Check point in convex polygon, O(logN) #define Det(a,b,c) ((double)(b.x-a.x)*(double)(c.y-a.y)-(double)(b.y-a.y)*(c.x-a.x)) PolygonLocation in_convex(vector<Point>& l, Point p){ if (l.empty()) return PolygonLocation::OUT; if (l.size() <= 2) { return onSegment(l[0], l[1 % l.size()], p) ? PolygonLocation::ON : PolygonLocation::OUT; } int a = 1, b = l.size()-1, c; if (Det(l[0], l[a], l[b]) > 0) swap(a,b); if (onSegment(l[0], l[a], p)) return ON; if (onSegment(l[0], l[b], p)) return ON; if (Det(l[0], l[a], p) > 0 || Det(l[0], l[b], p) < 0) return OUT; while(abs(a-b) > 1) { c = (a+b)/2; if (Det(l[0], l[c], p) > 0) b = c; else a = c; } int t = cmp(Det(l[a], l[b], p), 0); return (t == 0) ? ON : (t < 0) ? IN : OUT; } // Cut a polygon with a line. Returns half on left-hand-side. // To return the other half, reverse the direction of Line l (by negating l.a, l.b) // The line must be formed using 2 points Polygon polygon_cut(const Polygon& P, Line l) { Polygon Q; for(int i = 0; i < (int) P.size(); ++i) { Point A = P[i], B = (i == ((int) P.size())-1) ? P[0] : P[i+1]; if (ccw(l.A, l.B, A) != -1) Q.push_back(A); if (ccw(l.A, l.B, A)*ccw(l.A, l.B, B) < 0) { Point p; areIntersect(Line(A, B), l, p); Q.push_back(p); } } return Q; } // Find intersection of 2 convex polygons // Helper method bool intersect_1pt(Point a, Point b, Point c, Point d, Point &r) { double D = (b - a) % (d - c); if (cmp(D, 0) == 0) return false; double t = ((c - a) % (d - c)) / D; double s = -((a - c) % (b - a)) / D; r = a + (b - a) * t; return cmp(t, 0) >= 0 && cmp(t, 1) <= 0 && cmp(s, 0) >= 0 && cmp(s, 1) <= 0; } Polygon convex_intersect(Polygon P, Polygon Q) { const int n = P.size(), m = Q.size(); int a = 0, b = 0, aa = 0, ba = 0; enum { Pin, Qin, Unknown } in = Unknown; Polygon R; do { int a1 = (a+n-1) % n, b1 = (b+m-1) % m; double C = (P[a] - P[a1]) % (Q[b] - Q[b1]); double A = (P[a1] - Q[b]) % (P[a] - Q[b]); double B = (Q[b1] - P[a]) % (Q[b] - P[a]); Point r; if (intersect_1pt(P[a1], P[a], Q[b1], Q[b], r)) { if (in == Unknown) aa = ba = 0; R.push_back( r ); in = B > 0 ? Pin : A > 0 ? Qin : in; } if (C == 0 && B == 0 && A == 0) { if (in == Pin) { b = (b + 1) % m; ++ba; } else { a = (a + 1) % m; ++aa; } } else if (C >= 0) { if (A > 0) { if (in == Pin) R.push_back(P[a]); a = (a+1)%n; ++aa; } else { if (in == Qin) R.push_back(Q[b]); b = (b+1)%m; ++ba; } } else { if (B > 0) { if (in == Qin) R.push_back(Q[b]); b = (b+1)%m; ++ba; } else { if (in == Pin) R.push_back(P[a]); a = (a+1)%n; ++aa; } } } while ( (aa < n || ba < m) && aa < 2*n && ba < 2*m ); if (in == Unknown) { if (in_convex(Q, P[0])) return P; if (in_convex(P, Q[0])) return Q; } return R; } // Find the diameter of polygon. // Returns: // <diameter, <ids of 2 points>> pair<double, pair<int,int>> convex_diameter(const Polygon &p) { const int n = p.size(); int is = 0, js = 0; for (int i = 1; i < n; ++i) { if (p[i].y > p[is].y) is = i; if (p[i].y < p[js].y) js = i; } double maxd = (p[is]-p[js]).len(); int i, maxi, j, maxj; i = maxi = is; j = maxj = js; do { int ii = (i+1) % n, jj = (j+1) % n; if ((p[ii] - p[i]) % (p[jj] - p[j]) >= 0) j = jj; else i = ii; if ((p[i] - p[j]).len() > maxd) { maxd = (p[i] - p[j]).len(); maxi = i; maxj = j; } } while (i != is || j != js); return {maxd, std::minmax(maxi, maxj)}; /* farthest pair is (maxi, maxj). */ } // Pick theorem // Given non-intersecting polygon. // S = area // I = number of integer points strictly Inside // B = number of points on sides of polygon // S = I + B/2 - 1 #line 6 "Geometry/tests/aizu_cgl_4_a_polygon_convex_hull.test.cpp" void solve() { int n; cin >> n; Polygon g(n); for (auto& p : g) cin >> p; ConvexHull(g); int idx = 0; FOR(i,1,n-1) if (cmpy(g[i], g[idx])) idx = i; cout << g.size() << endl; REP(i,g.size()) cout << (fixed) << setprecision(0) << g[(idx + i) % g.size()] << '\n'; }