# Smallest enclosing circle

Dec 4th, 2021
838
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
1. struct SmallestEnclosingCircle {
2.     Circle getCircumcircle(Point a, Point b, Point c) {
3.         double d = 2.0 * (a.x * (b.y - c.y) + b.x * (c.y - a.y) + c.x * (a.y - b.y));
4.         assert(fabs(d) > EPS);
5.         double x = (a.norm() * (b.y - c.y) + b.norm() * (c.y - a.y) + c.norm() * (a.y - b.y)) / d;
6.         double y = (a.norm() * (c.x - b.x) + b.norm() * (a.x - c.x) + c.norm() * (b.x - a.x)) / d;
7.         Point p(x, y);
8.         return Circle(p, (p - a).len());
9.     }
10.     Circle getCircle(vector < Point > points) {
11.         assert(!points.empty());
12.         random_shuffle(points.begin(), points.end());
13.         Circle c(points[0], 0);
14.         int n = points.size();
15.         for (int i = 1; i < n; i++)
16.             if ((points[i] - c).len() > c.r + EPS) {
17.                 c = Circle(points[i], 0);
18.                 for (int j = 0; j < i; j++)
19.                     if ((points[j] - c).len() > c.r + EPS) {
20.                         c = Circle((points[i] + points[j]) / 2, (points[i] - points[j]).len() / 2);
21.                         for (int k = 0; k < j; k++)
22.                             if ((points[k] - c).len() > c.r + EPS)
23.                                 c = getCircumcircle(points[i], points[j], points[k]);
24.                     }
25.             }
26.         return c;
27.     }
28. };