⚙️AlgorithmIntermediate

Circle Geometry

Key Points

•
Circle geometry in computational geometry relies on precise vector math, quadratic equations, and careful floating-point handling with an EPS tolerance.
•
A point is inside, on, or outside a circle by comparing its distance to the center with the radius, typically using squared distances for speed and stability.
•
Line–circle intersection reduces to solving a quadratic; the discriminant tells you if there are 0, 1 (tangent), or 2 intersection points.
•
Circle–circle intersection is computed by locating the base point on the line of centers and stepping perpendicularly by a computed height.
•
External and internal tangents between two circles can be built with a unified vector formula that handles all four tangents.
•
The circumcircle passes through three non-collinear points; the incenter gives the incircle using side-length barycentric coordinates.
•
The minimum enclosing circle can be found in expected O(n) time with Welzl-style randomized algorithms, but robust EPS handling is essential.
•
Always guard against degenerate cases: coincident circles, collinear points for circumcircles, negative discriminants from numerical noise, and very small radii.

Prerequisites

→Vector arithmetic (2D) — Dot and cross products underpin distance, projections, and orientation tests used in circle operations.
→Quadratic equations — Line–circle intersection solves a quadratic whose discriminant classifies intersections.
→Floating-point stability — EPS comparisons prevent errors from rounding and near-degenerate configurations.
→Parametric lines — Intersections with circles are computed by substituting P(t) = P0 + tV into circle equations.
→Triangle geometry basics — Circumcircle and incircle formulas require side lengths, area relations, and perpendicular bisectors.

Detailed Explanation

Tap terms for definitions

01Overview

Circle geometry in algorithms focuses on representing circles precisely and performing reliable operations such as testing point positions, finding intersections with lines or other circles, computing tangents, and constructing special circles like the circumcircle and incircle. In programming contests and computational geometry libraries, circles are typically represented either by a center (cx, cy) with radius r, or by the general equation x^2 + y^2 + Dx + Ey + F = 0. From this foundation, many geometric queries reduce to vector arithmetic and solving small algebraic systems, often quadratics. A key practical challenge is floating-point robustness: instead of checking exact equality, we compare with a small tolerance EPS. This helps distinguish between ‘no intersection’ and ‘nearly tangent’ scenarios.

Typical tasks include: determining whether a point is inside/on/outside a circle; computing the points where a line meets a circle; intersecting two circles; constructing all common tangents; and building special circles of triangles (circumcircle, incircle). For optimization and clustering, the minimum enclosing circle (MEC) is a central tool and can be computed in expected linear time using randomized incremental algorithms (Welzl’s algorithm or its iterative equivalent). Mastery of dot/cross products, discriminants, and geometric invariants like the “power of a point” makes these operations both efficient and numerically stable.

02Intuition & Analogies

Imagine a circle as a ‘zone of reach’ of a Wi‑Fi router placed at the center: any phone within radius r gets signal (inside), on the border barely connects (on), and beyond is out of range (outside). If you walk along a straight path (a line), your path might miss the zone (no intersection), just graze it at one point (tangent), or pass through it entering and exiting (two intersections). The idea of solving a quadratic comes from projecting your straight path against this round zone: your position along the line (a single parameter) must satisfy the circle’s equation, producing a quadratic condition.

For two routers, their zones can overlap. If they are far apart, the zones don’t meet; if they barely touch, the contact point is a tangent; if they overlap, there are two crossing points. The exact scenario depends on the distance between centers compared to the sum and the absolute difference of radii. Tangent lines between two circles are like ‘tight ropes’ that just skim both zones—external tangents run outside both, while internal tangents pass between them.

For triangle-based circles, the circumcircle is the unique circle that passes through all three vertices—think of placing a tight ring that exactly touches the three corners. The incircle is like the biggest rubber disk that fits entirely inside the triangle while touching each side once. Finally, the minimum enclosing circle is the smallest disk that can cover a set of points—imagine shrinking a rubber band around nails on a board until it can’t shrink further; at the end, it’s supported by two or three nails (points).

03Formal Definition

A circle in the plane is the set of points P = (x, y) whose Euclidean distance to a fixed center C = (

c_{x}

c_{y}

) equals a fixed radius

r > 0 :

(x -

c_{x}

)^2 + (y -

c_{y}

)^2 =

r^{2}

. Equivalently, it can be expressed in general quadratic form

x^{2}

y^{2}

+ D x + E y +

F = 0

, where the center is C = (-D/2, -E/2) and

r^{2}

= (

D^{2}

E^{2}

)/4 - F. Given a point P, define the power of P with respect to a circle as pow(P) =

∣ P - C ∣

^2 -

r^{2}

. Then pow(P) < 0 means P is inside, = 0 means on,

an d > 0

means outside. For a line ℓ parameterized as L(t) = P0 + tV with

V \neq = 0

, intersection with a circle requires solving (P0 + tV - C)·(P0 + tV - C) =

r^{2}

, which yields a quadratic a

t^{2}

+ bt +

c = 0

where

a = V \cdot V

b = 2

V·(P0 - C), c =

∣ P 0 - C ∣

^2 -

r^{2}

. The discriminant Δ =

b^{2}

- 4ac classifies the intersection count. For two circles with centers C1, C2, radii r1, r2, let d =

∣ C 2 - C 1∣

. If

d > r 1 + r 2

or d <

∣ r 1 - r 2∣

there is no intersection; if

d = r 1 + r 2

or d =

∣ r 1 - r 2∣

there is a single tangent point; otherwise (and when the circles are not identical) there are exactly two intersection points. The radical axis of two circles is the locus of points with equal power to both circles and is a line obtained by subtracting their equations.

04When to Use

Use point–circle tests for quick containment queries (e.g., collision detection between a point-like object and a circular obstacle). Line–circle intersections appear in ray casting (visibility, rendering), computing shortest paths with obstacles, and clipping segments to circular boundaries. Circle–circle intersections and tangents show up in robotics (Minkowski sums, configuration spaces), VLSI layout, and contest problems where you must construct contact points or distances between round objects.

Triangle-related circles are staples of contest geometry: the circumcircle helps with angle chasing and arc properties, while the incircle provides shortest-distance and optimization insights; computationally, both are used for mesh generation and geometric predicates. The radical axis is useful for constructing common tangents and solving locus problems.

Minimum enclosing circle (MEC) is essential in clustering (1-center problem), facility location, bounding volumes for simulation/physics, and preprocessing for nearest-neighbor structures. In competitive programming, choose MEC via a randomized incremental algorithm for large n; for small n or debugging, even an O(n^3) brute over pairs/triples can suffice. Always adopt an EPS policy when comparing distances and discriminants to mitigate floating-point artifacts.

⚠️Common Mistakes

• Using exact equality on doubles (e.g., d == r): floating-point rounding makes this unreliable. Always compare with a tolerance EPS, and prefer squared distances to avoid unnecessary square roots. • Forgetting degenerate cases: coincident circles with the same radius (infinitely many intersection points), concentric circles with different radii (no intersection), or collinear triangle points (no circumcircle). Add explicit guards. • Mishandling negative discriminants by tiny margins: due to numerical noise, Δ can be slightly negative when theoretically zero. Clamp with max(Δ, 0) when constructing tangent or intersection points if |Δ| ≤ EPS. • Normalization errors in line parameterizations: mixing normalized and non-normalized direction vectors leads to wrong t values. Keep a consistent convention (either solve the quadratic with a = V·V or normalize V and adjust carefully). • Wrong sign in tangent formulations: internal vs external tangents differ by a sign; verify formulas and test symmetric cases (equal circles) to ensure you get four tangents when they exist. • Losing stability in circumcircle computation: solving near-parallel perpendicular bisectors can be unstable. Detect small area (|cross| near zero) and report no unique circle. • Ignoring orientation and cross product signs: many formulas rely on cross products; sign mistakes produce mirrored or swapped outputs. Write small helper functions for dot, cross, perp, and projection with unit tests.

Key Formulas

General Circle Equation

x^{2} + y^{2} + D x + E y + F = 0

Explanation: This is the quadratic form of a circle. Completing the squares gives the center C = (-D/2, -E/2) and radius r from D, E, F.

Center and Radius from General Form

C = (- \frac{D}{2}, - \frac{E}{2}), r^{2} = \frac{D ^{2} + E ^{2}}{4} - F

Explanation: Given D, E, F from the general equation, compute the geometric circle parameters. Valid only when $r^{2} > 0$ .

Power of a Point

pow (P) = ∥ P - C ∥^{2} - r^{2}

Explanation: A compact invariant for point–circle relations. Negative means inside, zero on, positive outside the circle.

Line–Circle Quadratic

a t^{2} + b t + c = 0, a = V \cdot V, b = 2 V \cdot (P_{0} - C), c = ∥ P_{0} - C ∥^{2} - r^{2}

Explanation: Substituting the line P(t) = P0 + tV into the circle gives a quadratic in t. Solve it to find line parameters at intersection points.

Discriminant

Δ = b^{2} - 4 a c

Explanation: If $Δ$ < 0 there is no real intersection, $Δ$ = 0 gives a tangent (one point), and $Δ$ > 0 yields two intersections.

Distance Between Centers

d = ∥ C_{2} - C_{1} ∥

Explanation: The relation between d, r1, and r2 determines whether two circles intersect, are tangent, or are separate/contained.

Circle–Circle Intersection Decomposition

a = \frac{r _{1}^{2} - r _{2}^{2} + d ^{2}}{2 d}, h = max {0, r_{1}^{2} - a^{2}}

Explanation: The base point lies a units from C1 along the line of centers, and h is the perpendicular offset to each intersection point.

Chord Length

L = 2 r^{2} - s^{2}

Explanation: If a chord is at distance s from the center, its length is L. Useful for arc and intersection segment computations.

Circumradius of Triangle

R = \frac{ab c}{4Δ}

Explanation: For side lengths a, b, c and triangle area $Δ$ , the circumradius R follows this formula. It appears in many geometric derivations.

Inradius of Triangle

r = \frac{2Δ}{a + b + c}

Explanation: The incircle radius r equals twice the triangle area divided by the perimeter. The incenter is at barycentric (a : b : c).

Circle Area and Perimeter

Area = π r^{2}, Circumference = 2 π r

Explanation: Basic measures of a circle. They often appear in optimization and geometry-of-measures problems.

Radical Axis Equation

Radical axis: (x^{2} + y^{2} + D_{1} x + E_{1} y + F_{1}) - (x^{2} + y^{2} + D_{2} x + E_{2} y + F_{2}) = 0

Explanation: Subtracting two circle equations cancels the quadratic terms, leaving a line of points with equal power to both circles.

Complexity Analysis

Most primitive circle operations run in constant time O(1): computing point–circle relations uses a few arithmetic operations; line–circle intersection reduces to solving a quadratic with constant work; circle–circle intersection uses a handful of vector operations and one or two square roots. Constructing circumcircle and incircle from a triangle also requires only constant time, involving dot/cross products and short linear solves. Enumerating all common tangents between two circles is O(1) given the closed-form vector formulas; you produce up to four tangent pairs. The stability cost is dominated by carefully handling EPS decisions and potential square-root of small negative values by clamping. The Minimum Enclosing Circle (MEC) via a randomized incremental algorithm is expected O(n) time and O(1) extra space beyond storing points. The practical implementation shuffles the input and maintains the smallest circle that covers processed points; when a point lies outside, it rebuilds the support from 2 or 3 boundary points. Although the worst-case time of the simple triple-loop incremental method is O(

n^{3}

), with randomization and the Helly-type property of disks, the expected number of boundary reconstructions remains small, yielding an expected linear runtime. Space complexity is O(1) auxiliary (a few points and circles), plus O(n) for the input itself. If you need to compute all pairwise circle–circle intersections for m circles, the naive approach is O(

m^{2}

). Similarly, generating tangents for many pairs is also quadratic in the number of pairs considered. When integrating these primitives into larger algorithms (e.g., visibility graphs), the overall complexity will be dominated by the number of segments/circles processed and graph size.

Code Examples

Core circle operations: point relation, line–circle intersection, and circle–circle intersection

1 #include <bits/stdc++.h>
2 using namespace std;
3 
4 const double EPS = 1e-9;
5 int sgn(double x){ return (x > EPS) - (x < -EPS); }
6 
7 struct Point {
8     double x, y;
9     Point() : x(0), y(0) {}
10     Point(double _x, double _y) : x(_x), y(_y) {}
11     Point operator+(const Point& o) const { return Point(x + o.x, y + o.y); }
12     Point operator-(const Point& o) const { return Point(x - o.x, y - o.y); }
13     Point operator*(double k) const { return Point(x * k, y * k); }
14     Point operator/(double k) const { return Point(x / k, y / k); }
15 };
16 
17 double dot(const Point& a, const Point& b){ return a.x*b.x + a.y*b.y; }
18 double cross(const Point& a, const Point& b){ return a.x*b.y - a.y*b.x; }
19 double norm2(const Point& a){ return dot(a, a); }
20 Point perp(const Point& a){ return Point(-a.y, a.x); }
21 
22 typedef Point Vec;
23 
24 struct Line { // P(t) = p + t*v
25     Point p; Vec v;
26     Line() {}
27     Line(Point _p, Vec _v): p(_p), v(_v) {}
28 };
29 
30 struct Circle {
31     Point c; double r;
32     Circle() : c(), r(0) {}
33     Circle(Point _c, double _r) : c(_c), r(_r) {}
34 };
35 
36 // Relation: -1 inside, 0 on, +1 outside
37 int pointCircleRelation(const Point& p, const Circle& C){
38     double val = norm2(p - C.c) - C.r*C.r;
39     int s = sgn(val);
40     if(s < 0) return -1;
41     if(s == 0) return 0;
42     return +1;
43 }
44 
45 // Intersect Line and Circle: return 0,1,2 points
46 vector<Point> intersectLineCircle(const Line& L, const Circle& C){
47     // Solve |(p + t v) - c|^2 = r^2  -> at^2 + bt + c0 = 0
48     Point p = L.p, c = C.c; Vec v = L.v;
49     double a = dot(v, v);
50     double b = 2.0 * dot(v, p - c);
51     double c0 = norm2(p - c) - C.r*C.r;
52     double D = b*b - 4*a*c0;
53     vector<Point> res;
54     if(D < -EPS) return res; // no intersection
55     D = max(0.0, D); // clamp small negatives
56     double sqrtD = sqrt(D);
57     double t1 = (-b - sqrtD) / (2*a);
58     double t2 = (-b + sqrtD) / (2*a);
59     Point i1 = p + v * t1;
60     res.push_back(i1);
61     if(sgn(D) > 0){
62         Point i2 = p + v * t2;
63         if(norm2(i2 - i1) > 1e-24) res.push_back(i2);
64     }
65     return res;
66 }
67 
68 // Intersect two circles: return 0,1,2 or infinite points (we report empty for infinite)
69 vector<Point> intersectCircleCircle(const Circle& A, const Circle& B){
70     vector<Point> res;
71     Point p1 = A.c, p2 = B.c; double r1 = A.r, r2 = B.r;
72     Vec dvec = p2 - p1;
73     double d2 = norm2(dvec);
74     double d = sqrt(d2);
75     // Coincident centers and equal radii -> infinite intersections
76     if(sgn(d) == 0 && sgn(r1 - r2) == 0) return res; // choose to return empty for infinite
77     // No intersection if too far or one inside another without touching
78     if(d > r1 + r2 + EPS) return res;
79     if(d + min(r1, r2) + EPS < max(r1, r2)) return res;
80     // Compute base point and offset
81     double a = (r1*r1 - r2*r2 + d*d) / (2*d);
82     double h2 = r1*r1 - a*a;
83     if(h2 < -EPS) return res;
84     h2 = max(0.0, h2);
85     Vec u = dvec / d; // unit along centers
86     Point base = p1 + u * a;
87     if(sgn(h2) == 0){ // tangent
88         res.push_back(base);
89         return res;
90     }
91     double h = sqrt(h2);
92     Vec w = perp(u) * h;
93     res.push_back(base + w);
94     res.push_back(base - w);
95     return res;
96 }
97 
98 int main(){
99     ios::sync_with_stdio(false);
100     cin.tie(nullptr);
101 
102     // Demo
103     Circle C(Point(0,0), 5.0);
104     Point P(3,4); // distance 5 -> on circle
105     cout << "Point relation to circle: " << pointCircleRelation(P, C) << "\n"; // 0
106 
107     Line L(Point(-10, 0), Vec(1, 0)); // horizontal line through y=0
108     auto pts1 = intersectLineCircle(L, C);
109     cout << "Line-circle intersections: " << pts1.size() << "\n";
110     for(auto &q: pts1) cout << fixed << setprecision(6) << q.x << " " << q.y << "\n";
111 
112     Circle C2(Point(6,0), 3.0);
113     auto pts2 = intersectCircleCircle(C, C2);
114     cout << "Circle-circle intersections: " << pts2.size() << "\n";
115     for(auto &q: pts2) cout << fixed << setprecision(6) << q.x << " " << q.y << "\n";
116     return 0;
117 }
118

This program builds a small geometry kernel with points, lines, and circles. It classifies a point with respect to a circle using squared distances, intersects a parameterized line with a circle by solving a quadratic, and intersects two circles by moving along the line of centers and stepping perpendicularly by the computed offset. EPS is used to stabilize comparisons and clamped discriminants avoid spurious negative values due to rounding.

Time: O(1) per operationSpace: O(1)

Tangents between two circles; circumcircle and incircle of a triangle

1 #include <bits/stdc++.h>
2 using namespace std;
3 
4 const double EPS = 1e-9;
5 int sgn(double x){ return (x > EPS) - (x < -EPS); }
6 
7 struct Point{
8     double x,y; Point() : x(0), y(0) {} Point(double _x,double _y):x(_x),y(_y){}
9     Point operator+(const Point& o) const { return Point(x+o.x,y+o.y); }
10     Point operator-(const Point& o) const { return Point(x-o.x,y-o.y); }
11     Point operator*(double k) const { return Point(x*k,y*k); }
12     Point operator/(double k) const { return Point(x/k,y/k); }
13 };
14 
15 double dot(const Point& a,const Point& b){ return a.x*b.x + a.y*b.y; }
16 double cross(const Point& a,const Point& b){ return a.x*b.y - a.y*b.x; }
17 double norm2(const Point& a){ return dot(a,a); }
18 Point perp(const Point& a){ return Point(-a.y, a.x); }
19 
20 struct Circle{ Point c; double r; Circle() : c(), r(0) {} Circle(Point _c,double _r):c(_c),r(_r){} };
21 
22 // Tangents between two circles. Each tangent is returned as the pair of touch points (on C1 and on C2).
23 vector<pair<Point,Point>> tangentsTwoCircles(const Circle& C1, const Circle& C2){
24     vector<pair<Point,Point>> res;
25     Point c1=C1.c, c2=C2.c; double r1=C1.r, r2=C2.r;
26     Point v = c2 - c1; double d2 = norm2(v);
27     if(d2 < EPS && fabs(r1 - r2) < EPS){
28         // Infinitely many common tangents (coincident circles) -> return empty per convention
29         return res;
30     }
31     for(int k : {-1, +1}){ // k = -1 -> internal, k = +1 -> external
32         double r = r2 * k - r1;
33         double h2 = d2 - r*r;
34         if(h2 < -EPS) continue; // no such tangents
35         Point u = v * (r) / d2; // base direction part
36         Point w = perp(v) * (sqrt(max(0.0, h2)) / d2);
37         for(int s : {-1, +1}){
38             Point dir = u + w * s; // direction from c1 to tangent point scaled by 1
39             Point p1 = c1 + dir * r1;
40             Point p2 = c2 + dir * (r2 * k);
41             res.push_back({p1, p2});
42             if(sgn(h2) == 0) break; // when h2==0, only one tangent per k
43         }
44     }
45     return res;
46 }
47 
48 // Line intersection helper: intersection of p + t*v and q + u*w
49 bool lineLineIntersection(Point p, Point v, Point q, Point w, Point &I){
50     double D = cross(v, w);
51     if(fabs(D) < EPS) return false; // parallel
52     double t = cross(q - p, w) / D;
53     I = p + v * t;
54     return true;
55 }
56 
57 // Circumcircle of triangle ABC. Returns false if collinear.
58 bool circumcircle(Point A, Point B, Point C, Circle &out){
59     // Perpendicular bisectors of AB and AC
60     Point midAB = (A + B) * 0.5, dAB = B - A; Point nAB = perp(dAB);
61     Point midAC = (A + C) * 0.5, dAC = C - A; Point nAC = perp(dAC);
62     Point O;
63     if(!lineLineIntersection(midAB, nAB, midAC, nAC, O)) return false;
64     out = Circle(O, sqrt(norm2(O - A)));
65     return true;
66 }
67 
68 // Incircle of triangle ABC: incenter and inradius
69 bool incircle(Point A, Point B, Point C, Circle &out){
70     // side lengths opposite A,B,C
71     double a = sqrt(norm2(B - C));
72     double b = sqrt(norm2(C - A));
73     double c = sqrt(norm2(A - B));
74     double per = a + b + c;
75     if(per < EPS) return false;
76     Point I = (A * a + B * b + C * c) / per;
77     // Distance from I to line AB as radius: r = |cross(B-A, I-A)| / |B-A|
78     double r = fabs(cross(B - A, I - A)) / max(EPS, sqrt(norm2(B - A)));
79     out = Circle(I, r);
80     return true;
81 }
82 
83 int main(){
84     ios::sync_with_stdio(false);
85     cin.tie(nullptr);
86 
87     Circle C1(Point(0,0), 2.0), C2(Point(6,1), 1.0);
88     auto tans = tangentsTwoCircles(C1, C2);
89     cout << "Tangents count: " << tans.size() << "\n";
90     cout.setf(std::ios::fixed); cout << setprecision(6);
91     for(size_t i=0;i<tans.size();++i){
92         auto [p1,p2] = tans[i];
93         cout << "Tangent " << i+1 << ": C1(" << p1.x << ", " << p1.y << ")  C2(" << p2.x << ", " << p2.y << ")\n";
94     }
95 
96     Point A(0,0), B(4,0), C(1,3);
97     Circle CC, IC;
98     if(circumcircle(A,B,C,CC)){
99         cout << "Circumcenter: " << CC.c.x << ", " << CC.c.y << "  R= " << CC.r << "\n";
100     } else cout << "No unique circumcircle (collinear).\n";
101 
102     if(incircle(A,B,C,IC)){
103         cout << "Incenter: " << IC.c.x << ", " << IC.c.y << "  r= " << IC.r << "\n";
104     } else cout << "No incircle (degenerate triangle).\n";
105     return 0;
106 }
107

The tangent construction uses a compact formula that unifies internal and external tangents by iterating over a sign k and computing two symmetric directions. Circumcircle is built from the intersection of two perpendicular bisectors; incircle uses incenter barycentric coordinates weighted by side lengths and the distance from the incenter to a side as the inradius.

Time: O(1) per constructionSpace: O(1)

Minimum Enclosing Circle (Welzl-style randomized incremental, expected O(n))

1 #include <bits/stdc++.h>
2 using namespace std;
3 
4 const double EPS = 1e-9;
5 int sgn(double x){ return (x > EPS) - (x < -EPS); }
6 
7 struct Point{
8     double x,y; Point():x(0),y(0){} Point(double _x,double _y):x(_x),y(_y){}
9     Point operator+(const Point& o) const { return Point(x+o.x,y+o.y); }
10     Point operator-(const Point& o) const { return Point(x-o.x,y-o.y); }
11     Point operator*(double k) const { return Point(x*k,y*k); }
12     Point operator/(double k) const { return Point(x/k,y/k); }
13 };
14 
15 double dot(const Point& a,const Point& b){ return a.x*b.x + a.y*b.y; }
16 double cross(const Point& a,const Point& b){ return a.x*b.y - a.y*b.x; }
17 double norm2(const Point& a){ return dot(a,a); }
18 
19 struct Circle{ Point c; double r; Circle():c(),r(-1){} Circle(Point _c,double _r):c(_c),r(_r){} };
20 
21 bool contains(const Circle& C, const Point& p){
22     if(C.r < 0) return false; // invalid circle
23     return norm2(p - C.c) <= C.r*C.r + 1e-12; // relaxed EPS for stability
24 }
25 
26 Circle circleFrom2(const Point& a, const Point& b){
27     Point c = (a + b) * 0.5;
28     double r = sqrt(norm2(a - b)) * 0.5;
29     return Circle(c, r);
30 }
31 
32 bool circleFrom3(const Point& A, const Point& B, const Point& C, Circle &out){
33     // circumcircle of triangle ABC; check collinearity
34     double D = 2.0 * (A.x*(B.y - C.y) + B.x*(C.y - A.y) + C.x*(A.y - B.y));
35     if(fabs(D) < EPS) return false; // collinear
36     double a2 = A.x*A.x + A.y*A.y;
37     double b2 = B.x*B.x + B.y*B.y;
38     double c2 = C.x*C.x + C.y*C.y;
39     double ux = (a2*(B.y - C.y) + b2*(C.y - A.y) + c2*(A.y - B.y)) / D;
40     double uy = (a2*(C.x - B.x) + b2*(A.x - C.x) + c2*(B.x - A.x)) / D;
41     Point O(ux, uy);
42     double r = sqrt(norm2(O - A));
43     out = Circle(O, r);
44     return true;
45 }
46 
47 // Randomized incremental MEC (expected O(n))
48 Circle minimumEnclosingCircle(vector<Point> pts){
49     // Shuffle for randomization
50     std::mt19937_64 rng(1234567); // fixed seed for reproducibility; change for true randomness
51     shuffle(pts.begin(), pts.end(), rng);
52     Circle C; // invalid initially (r < 0)
53     for(size_t i=0;i<pts.size();++i){
54         if(C.r >= 0 && contains(C, pts[i])) continue;
55         C = Circle(pts[i], 0.0);
56         for(size_t j=0;j<i;++j){
57             if(contains(C, pts[j])) continue;
58             C = circleFrom2(pts[i], pts[j]);
59             for(size_t k=0;k<j;++k){
60                 if(contains(C, pts[k])) continue;
61                 Circle tmp;
62                 if(circleFrom3(pts[i], pts[j], pts[k], tmp)) C = tmp;
63                 else {
64                     // Degenerate: fall back to max of pair circles
65                     Circle c1 = circleFrom2(pts[i], pts[j]);
66                     Circle c2 = circleFrom2(pts[i], pts[k]);
67                     Circle c3 = circleFrom2(pts[j], pts[k]);
68                     // Pick smallest covering all three
69                     vector<Circle> cs = {c1,c2,c3};
70                     Circle best; best.r = 1e300;
71                     for(auto &cc: cs){
72                         if(contains(cc, pts[i]) && contains(cc, pts[j]) && contains(cc, pts[k])){
73                             if(cc.r < best.r) best = cc;
74                         }
75                     }
76                     C = best;
77                 }
78             }
79         }
80     }
81     return C;
82 }
83 
84 int main(){
85     ios::sync_with_stdio(false);
86     cin.tie(nullptr);
87 
88     int n; cin >> n; vector<Point> pts(n);
89     for(int i=0;i<n;++i) cin >> pts[i].x >> pts[i].y;
90     Circle mec = minimumEnclosingCircle(pts);
91     cout.setf(std::ios::fixed); cout << setprecision(9);
92     cout << mec.c.x << " " << mec.c.y << " " << mec.r << "\n";
93     return 0;
94 }
95

This is an iterative, randomized incremental variant of Welzl’s algorithm. After shuffling, it maintains the smallest circle covering processed points; when a point is outside, it becomes a boundary point and the circle is rebuilt from one or two additional boundary points. The support of the final MEC is always 2 or 3 points. The implementation handles degenerate triples by falling back to the best of the pairwise diameter circles.

Time: Expected O(n); worst-case O(n^3) with this simple incremental structureSpace: O(1) extra (besides input)

1	#include <bits/stdc++.h>
2	using namespace std;
3
4	const double EPS = 1e-9;
5	int sgn(double x){ return (x > EPS) - (x < -EPS); }
6
7	struct Point {
8	double x, y;
9	Point() : x(0), y(0) {}
10	Point(double _x, double _y) : x(_x), y(_y) {}
11	Point operator+(const Point& o) const { return Point(x + o.x, y + o.y); }
12	Point operator-(const Point& o) const { return Point(x - o.x, y - o.y); }
13	Point operator(double k) const { return Point(x k, y * k); }
14	Point operator/(double k) const { return Point(x / k, y / k); }
15	};
16
17	double dot(const Point& a, const Point& b){ return a.xb.x + a.yb.y; }
18	double cross(const Point& a, const Point& b){ return a.xb.y - a.yb.x; }
19	double norm2(const Point& a){ return dot(a, a); }
20	Point perp(const Point& a){ return Point(-a.y, a.x); }
21
22	typedef Point Vec;
23
24	struct Line { // P(t) = p + t*v
25	Point p; Vec v;
26	Line() {}
27	Line(Point _p, Vec _v): p(_p), v(_v) {}
28	};
29
30	struct Circle {
31	Point c; double r;
32	Circle() : c(), r(0) {}
33	Circle(Point _c, double _r) : c(_c), r(_r) {}
34	};
35
36	// Relation: -1 inside, 0 on, +1 outside
37	int pointCircleRelation(const Point& p, const Circle& C){
38	double val = norm2(p - C.c) - C.r*C.r;
39	int s = sgn(val);
40	if(s < 0) return -1;
41	if(s == 0) return 0;
42	return +1;
43	}
44
45	// Intersect Line and Circle: return 0,1,2 points
46	vector<Point> intersectLineCircle(const Line& L, const Circle& C){
47	// Solve \|(p + t v) - c\|^2 = r^2 -> at^2 + bt + c0 = 0
48	Point p = L.p, c = C.c; Vec v = L.v;
49	double a = dot(v, v);
50	double b = 2.0 * dot(v, p - c);
51	double c0 = norm2(p - c) - C.r*C.r;
52	double D = bb - 4a*c0;
53	vector<Point> res;
54	if(D < -EPS) return res; // no intersection
55	D = max(0.0, D); // clamp small negatives
56	double sqrtD = sqrt(D);
57	double t1 = (-b - sqrtD) / (2*a);
58	double t2 = (-b + sqrtD) / (2*a);
59	Point i1 = p + v * t1;
60	res.push_back(i1);
61	if(sgn(D) > 0){
62	Point i2 = p + v * t2;
63	if(norm2(i2 - i1) > 1e-24) res.push_back(i2);
64	}
65	return res;
66	}
67
68	// Intersect two circles: return 0,1,2 or infinite points (we report empty for infinite)
69	vector<Point> intersectCircleCircle(const Circle& A, const Circle& B){
70	vector<Point> res;
71	Point p1 = A.c, p2 = B.c; double r1 = A.r, r2 = B.r;
72	Vec dvec = p2 - p1;
73	double d2 = norm2(dvec);
74	double d = sqrt(d2);
75	// Coincident centers and equal radii -> infinite intersections
76	if(sgn(d) == 0 && sgn(r1 - r2) == 0) return res; // choose to return empty for infinite
77	// No intersection if too far or one inside another without touching
78	if(d > r1 + r2 + EPS) return res;
79	if(d + min(r1, r2) + EPS < max(r1, r2)) return res;
80	// Compute base point and offset
81	double a = (r1r1 - r2r2 + dd) / (2d);
82	double h2 = r1r1 - aa;
83	if(h2 < -EPS) return res;
84	h2 = max(0.0, h2);
85	Vec u = dvec / d; // unit along centers
86	Point base = p1 + u * a;
87	if(sgn(h2) == 0){ // tangent
88	res.push_back(base);
89	return res;
90	}
91	double h = sqrt(h2);
92	Vec w = perp(u) * h;
93	res.push_back(base + w);
94	res.push_back(base - w);
95	return res;
96	}
97
98	int main(){
99	ios::sync_with_stdio(false);
100	cin.tie(nullptr);
101
102	// Demo
103	Circle C(Point(0,0), 5.0);
104	Point P(3,4); // distance 5 -> on circle
105	cout << "Point relation to circle: " << pointCircleRelation(P, C) << "\n"; // 0
106
107	Line L(Point(-10, 0), Vec(1, 0)); // horizontal line through y=0
108	auto pts1 = intersectLineCircle(L, C);
109	cout << "Line-circle intersections: " << pts1.size() << "\n";
110	for(auto &q: pts1) cout << fixed << setprecision(6) << q.x << " " << q.y << "\n";
111
112	Circle C2(Point(6,0), 3.0);
113	auto pts2 = intersectCircleCircle(C, C2);
114	cout << "Circle-circle intersections: " << pts2.size() << "\n";
115	for(auto &q: pts2) cout << fixed << setprecision(6) << q.x << " " << q.y << "\n";
116	return 0;
117	}
118