Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- struct SmallestEnclosingCircle {
- Circle getCircumcircle(Point a, Point b, Point 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());
- }
- 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;
- }
- };
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement