Minimum circle coverage (basis of computational geometry)

Portal

Ideas ：

① randomization Point set （ Reduces complexity ）

② Initially, find two points at random , Set to    and   , With     and    Make an initial circle for the diameter   ( With   Indicates before overwriting i The smallest circle of a point ).

③ Add new points in turn , If the current point    In the circle    in , be   , Otherwise, we should    Make a circle as the end point of the new diameter   ( Obviously On the boundary of the new circle ).

④ But the new round    It doesn't necessarily include all the previous i A little bit , So we went through the search and found i One point is not in    In the point   , So a little    and    It must be on the boundary of the new circle , So directly    Make a new circle for the diameter  .

⑤ Again    It doesn't necessarily include all the previous j A little bit , So find another point  , Be sure  ,,  On the boundary of the new circle , Then we can find this Circumscribed circle of three points That is, get a new circle   .

⑥ The circle obtained by these three cycles is called coverage At present The smallest circle of all points .

⑦ I don't know why randomization reduces complexity , Here's the big guy's proof ：

For other specific ideas and proofs, see other Big blog .

Code implementation ：

#include<bits/stdc++.h>
#define endl '\n'
#define null NULL
#define ll long long
#define int long long
#define pii pair<int, int>
#define lowbit(x) (x &(-x))
#define ls(x) x<<1
#define rs(x) (x<<1+1)
#define me(ar) memset(ar, 0, sizeof ar)
#define mem(ar,num) memset(ar, num, sizeof ar)
#define rp(i, n) for(int i = 0, i < n; i ++)
#define rep(i, a, n) for(int i = a; i <= n; i ++)
#define pre(i, n, a) for(int i = n; i >= a; i --)
#define IOS ios::sync_with_stdio(0); cin.tie(0);cout.tie(0);
const int way[4][2] = {
   {1, 0}, {-1, 0}, {0, 1}, {0, -1}};
using namespace std;
const int  inf = 0x3f3f3f3f3f3f3f3f;
const double PI = acos(-1.0);
const double eps = 1e-6;
const ll   mod = 1e9+7;
const int  N = 2e5 + 5;

inline void read(int &x){
    char t=getchar();
    while(!isdigit(t)) t=getchar();
    for(x=t^48,t=getchar();isdigit(t);t=getchar()) x=x*10+(t^48);
}

int n;
double r;

struct node{
    double x, y;
}o, a[N];

double dis(node a, node b){   // Get the distance between two points 
    return sqrt((a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y));
}

void get(node a, node b, node c){   // Three points determine a circle 
    double x1 = a.x-b.x, y1 = a.y-b.y;
    double d1 = (a.x*a.x-b.x*b.x+a.y*a.y-b.y*b.y)/2;
    double x2 = a.x-c.x, y2 = a.y-c.y;
    double d2 = (a.x*a.x-c.x*c.x+a.y*a.y-c.y*c.y)/2;
    o.x = (d1*y2-y1*d2)/(x1*y2-y1*x2);
    o.y = (d2*x1-x2*d1)/(x1*y2-y1*x2);
    r = dis(o, a);
}

signed main()
{
    IOS;

    cin >> n;
    for(int i = 1; i <= n; i ++)
        cin >> a[i].x >> a[i].y;
    random_shuffle(a+1, a+n+1);
    o = a[1];  // Take the first point as the center of the circle 
    for(int i = 2; i <= n; i ++){
        if(dis(o, a[i])>r+eps){   // Find the first point not in the circle 
            o = {(a[1].x+a[i].x)/2, (a[1].y+a[i].y)/2};  // Update center point 
            r = dis(o, a[i]);     // Update radius 
            for(int j = 1; j < i; j ++){
                if(dis(o, a[j])>r+eps){    // Find the second point not in the circle 
                    o = {(a[i].x+a[j].x)/2, (a[i].y+a[j].y)/2};   // Update center point 
                    r = dis(o, a[j]);    // Update radius 
                    for(int k = 1; k <j; k ++){
                        if(dis(o, a[k])>r+eps){   // Find the third point that is not in the circle 
                            get(a[i], a[j], a[k]);    // Three points outside the circle to update the smallest circle 
                        }
                    }
                }
            }
        }
    }
    printf("%.10f\n%.10f %.10f\n", r, o.x, o.y);

    return 0;
}