This documentation is automatically generated by online-judge-tools/verification-helper
View the Project on GitHub ngthanhtrung23/ACM_Notebook_new
// Smallest enclosing circle: // Given N points. Find the smallest circle enclosing these points. // Amortized complexity: O(N) // // Tested: // - https://www.spoj.com/problems/ALIENS/ // - https://www.spoj.com/problems/QCJ4/ // - https://www.acmicpc.net/problem/2626 // - https://oj.vnoi.info/problem/icpc22_mt_l struct SmallestEnclosingCircle { Circle getCircle(vector<Point> points) { assert(!points.empty()); random_shuffle(points.begin(), points.end()); Circle c(points[0], 0); int n = points.size(); for (int i = 1; i < n; i++) if ((points[i] - c).len() > c.r + EPS) { c = Circle(points[i], 0); for (int j = 0; j < i; j++) if ((points[j] - c).len() > c.r + EPS) { c = Circle((points[i] + points[j]) / 2, (points[i] - points[j]).len() / 2); for (int k = 0; k < j; k++) if ((points[k] - c).len() > c.r + EPS) c = getCircumcircle(points[i], points[j], points[k]); } } return c; } // NOTE: This code work only when a, b, c are not collinear and no 2 points are same --> DO NOT // copy and use in other cases. Circle getCircumcircle(Point a, Point b, Point c) { assert(a != b && b != c && a != c); assert(ccw(a, b, c)); double d = 2.0 * (a.x * (b.y - c.y) + b.x * (c.y - a.y) + c.x * (a.y - b.y)); assert(fabs(d) > EPS); double x = (a.norm() * (b.y - c.y) + b.norm() * (c.y - a.y) + c.norm() * (a.y - b.y)) / d; double y = (a.norm() * (c.x - b.x) + b.norm() * (a.x - c.x) + c.norm() * (b.x - a.x)) / d; Point p(x, y); return Circle(p, (p - a).len()); } };
#line 1 "Geometry/smallestEnclosingCircle.h" // Smallest enclosing circle: // Given N points. Find the smallest circle enclosing these points. // Amortized complexity: O(N) // // Tested: // - https://www.spoj.com/problems/ALIENS/ // - https://www.spoj.com/problems/QCJ4/ // - https://www.acmicpc.net/problem/2626 // - https://oj.vnoi.info/problem/icpc22_mt_l struct SmallestEnclosingCircle { Circle getCircle(vector<Point> points) { assert(!points.empty()); random_shuffle(points.begin(), points.end()); Circle c(points[0], 0); int n = points.size(); for (int i = 1; i < n; i++) if ((points[i] - c).len() > c.r + EPS) { c = Circle(points[i], 0); for (int j = 0; j < i; j++) if ((points[j] - c).len() > c.r + EPS) { c = Circle((points[i] + points[j]) / 2, (points[i] - points[j]).len() / 2); for (int k = 0; k < j; k++) if ((points[k] - c).len() > c.r + EPS) c = getCircumcircle(points[i], points[j], points[k]); } } return c; } // NOTE: This code work only when a, b, c are not collinear and no 2 points are same --> DO NOT // copy and use in other cases. Circle getCircumcircle(Point a, Point b, Point c) { assert(a != b && b != c && a != c); assert(ccw(a, b, c)); double d = 2.0 * (a.x * (b.y - c.y) + b.x * (c.y - a.y) + c.x * (a.y - b.y)); assert(fabs(d) > EPS); double x = (a.norm() * (b.y - c.y) + b.norm() * (c.y - a.y) + c.norm() * (a.y - b.y)) / d; double y = (a.norm() * (c.x - b.x) + b.norm() * (a.x - c.x) + c.norm() * (b.x - a.x)) / d; Point p(x, y); return Circle(p, (p - a).len()); } };