Merevoli

Smallest enclosing circle

Dec 4th, 2021
673
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. };
RAW Paste Data