TIOJ 1093 . B.古力德

Least Cover Circle

#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <algorithm>
#include <cassert>
#include <vector>

using namespace std;

const double eps = 1e-7;
const double inf = 1e7;

bool db_eq(const double& a, const double& b){return fabs(a-b)<=eps;}
bool db_bt(const double& a, const double& b){return a>b+eps;}
bool db_st(const double& a, const double& b){return a+eps<b;}

struct pt{
    double x, y;
    pt(double _x = 0, double _y = 0): x(_x), y(_y){}
    double len()const{return sqrt(x*x+y*y);}
};

pt operator+(const pt& a, const pt& b){return pt(a.x+b.x, a.y+b.y);}
pt operator-(const pt& a, const pt& b){return pt(a.x-b.x, a.y-b.y);}
pt operator/(const pt& a, const double& r){return pt(a.x/r, a.y/r);}
double operator^(const pt& a, const pt& b){return a.x*b.y-a.y*b.x;}
pt operator~(const pt& a){return pt(a.y, -a.x);}

struct line{
    // ax + by + c = 0;
    double a, b, c;
    line(){
        a = 0, b = 0, c = 0;
    }
    line(const pt& m, const pt& s){
        a = m.y, b = -m.x;
        c = -(a*s.x+b*s.y);
    }
    pt m()const{
        return pt(-b, a);
    }
};

pt operator*(const line& l1, const line& l2){
    double det = l1.m()^l2.m();
    if(db_eq(det, 0)) return pt(inf, inf);
    double detx = -l1.c*l2.b+l2.c*l1.b;
    double dety =  l1.c*l2.a-l2.c*l1.a;
    return pt(detx/det, dety/det);
}

struct cir{
    pt o;
    double r;
    cir(const pt& _o = pt(), const double& _r = 0): o(_o), r(_r){}
    cir(const pt& pt1, const pt& pt2){o = (pt1+pt2)/2; r = (pt1-o).len();}
   
    cir(const pt& pt1, const pt& pt2, const pt& pt3){
        line l1 = line(~(pt2-pt1), (pt1+pt2)/2);
        line l2 = line(~(pt3-pt1), (pt1+pt3)/2);
        o = l1*l2;
        if(db_eq(o.x, inf)){
            double l12 = (pt1-pt2).len(),
                   l23 = (pt2-pt3).len(),
                   l13 = (pt3-pt1).len();
            if(db_eq(l12+l23,l13)) cir(pt1,pt3);
            else if(db_eq(l13+l23,l12)) cir(pt1,pt2);
            else if(db_eq(l12+l13,l23)) cir(pt2,pt3);
            else assert(0);
        }else{
            r = (o-pt1).len();
        }
    }
    bool has(const pt& p){ return db_bt((p-o).len(),r) == false;}
};

cir lcc2(vector<pt>& inp, int lim, const pt& pt1, const pt& pt2){
    cir ret(pt1, pt2);
    for(int lx = 0;lx < lim;lx++)
        if(ret.has(inp[lx]) == false)
            ret = cir(pt1, pt2, inp[lx]);
    return ret;
}

cir lcc1(vector<pt>& inp, int lim, const pt& pt){
    cir ret(inp[0], pt);
    for(int lx = 1;lx < lim;lx++)
        if(ret.has(inp[lx]) == false)
            ret = lcc2(inp, lx, pt, inp[lx]);
    return ret;
}

cir lcc(vector<pt>& inp){
    random_shuffle(inp.begin(), inp.end());
    cir ret(inp[0], inp[1]);
    for(int lx = 2;lx < inp.size();lx++)
        if(ret.has(inp[lx]) == false)
            ret = lcc1(inp, lx, inp[lx]);
    return ret;
}

int main(){
    int n, m;
    for(;;){
        scanf("%d %d", &n, &m);
        if(n == 0 and m == 0) break;
        vector<pt> inp(m);
        for(int lx = 0;lx < m;lx++)
            scanf("%lf %lf", &inp[lx].x, &inp[lx].y);
        printf("%.3f\n", lcc(inp).r);
    }
    return 0;
}