P1742 最小圆覆盖 （计算几何）

题目链接

题面：

题解：
求最小圆覆盖。
随机增量法，期望复杂度O（n）。
先将所有的点随机打乱。
定理1： 如果点p不在集合S的最小覆盖圆内，则p一定在S∪{p}的最小覆盖圆上。

根据这个定理，我们可以分三个for确定前i个点的最小覆盖圆。

1.令前i-1个点的最小覆盖圆为C
2.如果第i个点在C内（包括边界），则前i个点的最小覆盖圆也是C
3.如果不在，那么第i个点一定在前i个点的最小覆盖圆上，接着确定前i−1个点中还有哪两个在最小覆盖圆上。因此，设当前圆心为Pi，半径为0，做固定了第i个点的前i个点的最小圆覆盖。
4.固定了一个点–去找第二个点：不停地在范围内找到第一个不在当前最小圆上的点Pj ，当前圆心为(Pi+Pj)/2半径为1/2 | Pi Pj | 做固定了两个点的，前 j 个点外加第 i 个点的最小圆覆盖。
5.固定了两个点–去找第三个点：不停地在范围内找到第一个不在当前最小圆上的点Pk，当前圆为Pi , Pj , Pk 的外接圆。

用random_shuffle随机打乱会wa两个点。。。
真感谢知乎上见到的O（n）随机数列。

从后往前遍历，对于每一个 p [ i ]，随机与它前面的一个数交换。

#include<iostream>
#include<cstdlib>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<string>
#include<cmath>
#include<queue>
#include<map>
#include<vector>
#define ll long long
#define llu unsigned ll
using namespace std;

const double eps=1e-8;
const double dnf=1e20;
const double pi=acos(-1.0);
const int maxp=100100;

//浮点型数值是否为0
int sgn(double x)
{
    if(abs(x)<eps) return 0;
    if(x<0) return -1;
    return 1;
}


//返回x的平方
double sqr(double x)
{
    return x*x;
}

//二维点
struct Point
{
    double  x,y;
    Point(){}
    Point(double xx,double yy)
    {
        x=xx,y=yy;
    }

    //输入输出
    void input(void)
    {
        scanf("%lf%lf",&x,&y);
    }
    void output(void)
    {
        printf("%.2f %.2f\n",x,y);
    }

    //重载比较运算符
    bool operator == (const Point &b) const
    {
        return sgn(x-b.x)==0&&sgn(y-b.y)==0;
    }

    bool operator < (const Point &b) const
    {
        if(sgn(x-b.x)!=0) return x<b.x;
        else return sgn(y-b.y)<0;
    }

    //重载加减乘除
    Point operator + (const Point &b) const
    {
        return Point(x+b.x,y+b.y);
    }

    Point operator - (const Point &b) const
    {
        return Point(x-b.x,y-b.y);
    }

    Point operator * (const double &k) const
    {
        return Point(x*k,y*k);
    }

    Point operator / (const double &k) const
    {
        return Point(x/k,y/k);
    }

    //叉乘，叉积
    double operator ^ (const Point &b) const
    {
        return x*b.y-y*b.x;
    }
    //点乘，点积
    double operator * (const Point &b) const
    {
        return x*b.x+y*b.y;
    }

    //长度
    double len(void)
    {
        return hypot(x,y);
    }

    //长度的平方
    double len2(void)
    {
        return x*x+y*y;
    }

    //两点距离
    double dis(const Point &b) const
    {
        return hypot(x-b.x,y-b.y);
    }

    //计算pa，pb的夹角，就是这个点看a，b形成的角度
    double rad(const Point &a,const Point &b)const
    {
        Point p=*this;
        return abs(atan2(abs((a-p)^(b-p)),(a-p)*(b-p)));
    }

    //化向量长度为r
    Point turn_to_r(double r)
    {
        double l=len();
        if(!sgn(l)) return *this;
        r/=l;
        return Point(x*r,y*r);
    }

    //逆时针转90
    Point turn_left(void)
    {
        return Point(-y,x);
    }

    //顺时针转90
    Point turn_right(void)
    {
        return Point(y,-x);
    }

    //绕p点逆时针转angle
    Point turn_p_angle(const Point &p,double angle)
    {
        Point v=(*this)-p;
        double c=cos(angle),s=sin(angle);
        return Point(p.x+v.x*c-v.y*s,p.y+v.x*s+v.y*c);
    }

};

//****************************************************************
//****************************************************************

struct Line
{
    Point s,e;
    Line(){}

    //两点
    Line(const Point ss,const Point ee)
    {
        s=ss,e=ee;
    }

    //点斜
    Line(const Point p,const double angle)
    {
        s=p;
        if(sgn(angle-pi/2)==0)
            e=(s+Point(0,1));
        else e=(s+Point(1,tan(angle)));
    }

    //ax+by+c=0
    Line(double a,double b,double c)
    {
        if(sgn(a)==0)
        {
            s=Point(0,-c/b);
            e=Point(1,-c/b);
        }
        else if(sgn(b)==0)
        {
            s=Point(-c/a,0);
            e=Point(-c/a,1);
        }
        else
        {
            s=Point(0,-c/b);
            e=Point(1,(-c-a)/b);
        }
    }

    void input(void)
    {
        s.input();
        e.input();
    }

    void output(void)
    {
        s.output();
        e.output();
    }

    //两点应该是由s——>e,
    //由x负向指向x正向。
    void adjust(void)
    {
        if(e<s) swap(s,e);
    }

    //判断两线段是否重合
    bool operator == (Line b)
    {
        adjust(),b.adjust();
        return (s==b.s)&&(e==b.e);
    }

    //求线段长度
    double len(void)
    {
        return s.dis(e);
    }

    //返回直线倾斜角
    //0<=angle<pi
    double angle(void)
    {
        double k=atan2(e.y-s.y,e.x-s.x);
        if(sgn(k)<0) k+=pi;
        if(sgn(k-pi)==0) k-=pi;
        return k;
    }

    //点和直线的关系
    //1 在左侧 （在s——>e的逆时针侧）
    //2 在右侧 （在s——>e的顺时针侧）
    //3 在直线上
    int relation(const Point &p)
    {
        int c=sgn((p-s)^(e-s));
        if(c<0) return 1;
        else if(c>0) return 2;
        else return 3;
    }

    //点是否在线段上
    bool p_is_on_seg(const Point &p)
    {
        return sgn((p-s)^(e-s))==0&&sgn((p-s)*(p-e))<=0;
    }

    //两向量平行，对应直线平行或者重合
    bool parallel(const Line &v)
    {
        return sgn((e-s)^(v.e-v.s))==0;
    }

    //两线段相交判断
    //2 规范相交
    //1 非规范相交
    //0 不相交
    int seg_cross_seg(const Line &v)
    {
        int d1=sgn((e-s)^(v.s-s));
        int d2=sgn((e-s)^(v.e-s));
        int d3=sgn((v.e-v.s)^(s-v.s));
        int d4=sgn((v.e-v.s)^(e-v.s));
        if((d1^d2)==-2&&(d3^d4)==-2) return 2;
        d1=(d1==0&&sgn((v.s-s)*(v.s-e))<=0);
        d2=(d2==0&&sgn((v.e-s)*(v.e-e))<=0);
        d3=(d3==0&&sgn((s-v.s)*(s-v.e))<=0);
        d4=(d4==0&&sgn((e-v.s)*(e-v.e))<=0);
        return d1||d2||d3||d4;
    }

    //直线和线段相交
    //2 规范相交
    //1 非规范相交
    //0 不相交
    int line_cross_seg(const Line &v)
    {
        int d1=sgn((e-s)^(v.s-s));
        int d2=sgn((e-s)^(v.e-s));
        if(d1^d2==-2) return 2;
        return (d1==0||d2==0);
    }

    //两直线的关系
    //0 平行
    //1 重合
    //2 相交
    int line_cross_line(Line &v)
    {
        if((*this).parallel(v))
            return v.relation(s)==3;
        return 2;
    }

    //求两直线的交点
    //要保证两直线不平行或重合
    Point cross_point(Line v)
    {
        double a1=(v.e-v.s)^(s-v.s);
        double a2=(v.e-v.s)^(e-v.s);
        return Point((s.x*a2-e.x*a1)/(a2-a1),(s.y*a2-e.y*a1)/(a2-a1));
    }

    //点到直线的距离
    double dis_point_to_line(const Point &p)
    {
        return abs((p-s)^(e-s))/len();
    }

    //点到线段的距离
    double dis_point_to_seg(const Point &p)
    {
        if(sgn((p-s)*(e-s))<0||sgn((p-e)*(s-e))<0)
            return min(p.dis(s),p.dis(e));
        return dis_point_to_line(p);
    }

    //返回线段到线段的距离
    //前提是两线段不相交，相交就是0了
    double dis_seg_to_seg(Line &v)
    {
        double s1=min(dis_point_to_seg(v.s),dis_point_to_seg(v.e));
        double s2=min(v.dis_point_to_seg(s),v.dis_point_to_seg(e));
        return min(s1,s2);
    }

    //返回点p在直线上的投影
    Point point_proj_line(Point &p)
    {
        return s+(((e-s)*((e-s)*(p-s)))/((e-s).len2()));
    }

    //返回点p关于直线的对称点
    Point point_sym_line(Point &p)
    {
        Point q=point_proj_line(p);
        return Point(2*q.x-p.x,2*q.y-p.y);
    }
};

//****************************************************************
//****************************************************************

struct circle
{
    Point p;
    double r;
    circle(){}
    circle(Point pp,double rr)
    {
        p=pp,r=rr;
    }
    circle(double xx,double yy,double rr)
    {
        p=Point(xx,yy);
        r=rr;
    }

    //三角形外接圆
    //利用两条边的中垂线得到圆心
    circle(Point a,Point b,Point c)
    {
        Line u=Line((a+b)/2,((a+b)/2)+((b-a).turn_left()));
        Line v=Line((b+c)/2,((b+c)/2)+((c-b).turn_left()));
        p=u.cross_point(v);
        r=p.dis(a);
    }

    //三角形内切圆，bool t只是为了重载
    circle(Point a,Point b,Point c,bool t)
    {
        Line u,v;
        double m=atan2(b.y-a.y,b.x-a.x),n=atan2(c.y-a.y,c.x-a.x);
        u.s=a;
        u.e=u.s+Point(cos((n+m)/2),sin((n+m)/2));
        m=atan2(a.y-b.y,a.x-b.x),n=atan2(c.y-b.y,c.x-b.x);
        v.s=b;
        v.e=v.s+Point(cos((n+m)/2),sin((n+m)/2));
        p=u.cross_point(v);
        r=Line(a,b).dis_point_to_seg(p);
    }

    circle max(circle b)
    {
        if(r>b.r) return *(this);
        return b;
    }

    void input(void)
    {
        p.input();
        scanf("%lf",&r);
    }

    void output(void)
    {
        printf("%.2f %.2f %.2f\n",p.x,p.y,r);
    }

    bool operator == (const circle &v)
    {
        return (p==v.p)&&sgn(r-v.r)==0;
    }

    bool operator <(const circle &v) const
    {
        return ((p<v.p)||((p==v.p)&&sgn(r-v.r)<0));
    }

    double area(void)
    {
        return pi*r*r;
    }

    double cir(void)
    {
        return 2*pi*r;
    }

    //点和圆的关系，
    //0 圆外
    //1 圆上
    //2 圆内
    int rel_of_point(const Point &b)
    {
        double dist=b.dis(p);
        if(sgn(dist-r)<0) return 2;
        if(sgn(dist-r)==0) return 1;
        return 0;
    }

    //线段和圆的关系
    //比较的是圆心到线段的距离和半径的关
    int rel_of_seg(Line &v)
    {
        double dist=v.dis_point_to_seg(p);
        if(sgn(dist-r)<0) return 2;
        if(sgn(dist-r)==0) return 1;
        return 0;
    }

    //直线和圆的关系
    //比较的是圆心到直线的距离和半径的关系
    int rel_of_line(Line &v)
    {
        double dist=v.dis_point_to_line(p);
        if(sgn(dist-r)<0) return 2;
        if(sgn(dist-r)==0) return 1;
        return 0;
    }
    //两圆的关系
    //5 相离
    //4 外切
    //3 相交
    //2 内切
    //1 内含
    int rel_of_circle(const circle &v)
    {
        double d=p.dis(v.p);
        if(sgn(d-r-v.r)>0) return 5;
        if(sgn(d-r-v.r)==0) return 4;
        double l=abs(r-v.r);
        if(sgn(d-r-v.r)<0&&sgn(d-l)>0) return 3;
        if(sgn(d-l)==0) return 2;
        if(sgn(d-l)<0) return 1;
    }

    //求两个圆的交点,
    //0 表示没有交点，
    //1 是一个交点，
    //2 是两个交点
    int point_two_circle(const circle &v,Point &p1,Point &p2)
    {
        int rel=rel_of_circle(v);
        if(rel==1||rel==5) return 0;
        double d=p.dis(v.p);
        double l=(d*d+r*r-v.r*v.r)/(2*d);
        double h=sqrt(r*r-l*l);
        Point tmp=p+(v.p-p).turn_to_r(l);
        p1=tmp+((v.p-p).turn_left().turn_to_r(h));
        p2=tmp+((v.p-p).turn_right().turn_to_r(h));
        if(rel==2||rel==4) return 1;
        return 2;
    }

    //求直线和圆的交点，返回交点个数
    int point_line_circle(Line &v,Point &p1,Point &p2)
    {
        if(!(*this).rel_of_line(v)) return 0;
        Point a=v.point_proj_line(p);
        double d=v.dis_point_to_line(p);
        d=sqrt(r*r-d*d);
        if(sgn(d)==0)
        {
            p1=a;
            p2=a;
            return 1;
        }
        p1=a+(v.e-v.s).turn_to_r(d);
        p2=a-(v.e-v.s).turn_to_r(d);
        return 2;
    }

    //得到过 a,b 两点，半径为 r1 的两个圆
    int circle_by_point_point_r(Point a,Point b,double r1,circle &c1,circle &c2)
    {
        circle x(a,r1),y(b,r1);
        int t=x.point_two_circle(y,c1.p,c2.p);
        if(!t) return 0;
        c1.r=c2.r=r;
        return t;
    }

    //得到与直线 u 相切，过点 q, 半径为 r1 的圆
    int circle_by_line_point_r(Line u,Point q,double r1,circle &c1,circle &c2)
    {
        double dis=u.dis_point_to_line(q);
        if(sgn(dis-r1*2)>0) return 0;
        if(sgn(dis)==0)
        {
            c1.p=q+((u.e-u.s).turn_left().turn_to_r(r1));
            c2.p=q+((u.e-u.s).turn_right().turn_to_r(r1));
            c1.r=c2.r=r1;
            return 2;
        }
        Line u1=Line((u.s+(u.e-u.s).turn_left().turn_to_r(r1)),(u.e+(u.e-u.s).turn_left().turn_to_r(r1)));
        Line u2=Line((u.s+(u.e-u.s).turn_right().turn_to_r(r1)),(u.e+(u.e-u.s).turn_right().turn_to_r(r1)));
        circle cc=circle(q,r1);
        Point p1,p2;
        if(!cc.point_line_circle(u1,p1,p2)) cc.point_line_circle(u2,p1,p2);
        c1=circle(p1,r1);
        if(p1==p2)
        {
            c2=c1;
            return 1;
        }
        c2=circle(p2,r1);
        return 2;
    }

    //同时与直线 u,v 相切，半径为 r1 的圆
    int circle_by_line_line_r(Line u,Line v,double r1,circle &c1,circle &c2,circle &c3,circle &c4)
    {
        if(u.parallel(v)) return 0;
        Line u1=Line(u.s+(u.e-u.s).turn_left().turn_to_r(r1),u.e+(u.e-u.s).turn_left().turn_to_r(r1));
        Line u2=Line(u.s+(u.e-u.s).turn_right().turn_to_r(r1),u.e+(u.e-u.s).turn_right().turn_to_r(r1));
        Line v1=Line(v.s+(v.e-v.s).turn_left().turn_to_r(r1),v.e+(v.e-v.s).turn_left().turn_to_r(r1));
        Line v2=Line(v.s+(v.e-v.s).turn_right().turn_to_r(r1),v.e+(v.e-v.s).turn_right().turn_to_r(r1));

        c1.r=c2.r=c3.r=c4.r=r1;
        c1.p=u1.cross_point(v1);
        c2.p=u1.cross_point(v2);
        c3.p=u2.cross_point(v1);
        c4.p=u2.cross_point(v2);
        return 4;
    }

    //同时与不相交圆 cx,cy 相切，半径为 r1 的圆
    int circle_by_circle_circle_r(circle cx,circle cy,double r1,circle &c1,circle &c2)
    {
        circle x(cx.p,r1+cx.r),y(cy.p,r1+cy.r);
        int t=x.point_two_circle(y,c1.p,c2.p);
        if(!t) return 0;
        c1.r=c2.r=r1;
        return t;
    }

    //过一点作圆的切线 (先判断点和圆的关系)
    int tangentline(Point q,Line &u,Line &v)
    {
        int x=rel_of_point(q);
        if(x==2) return 0;
        if(x==1)
        {
            u=Line(q,q+(q-p).turn_left());
            v=u;
            return 1;
        }
        double d=p.dis(q);
        double l=r*r/d;
        double h=sqrt(r*r-l*l);
        u=Line(q,p+((q-p).turn_to_r(l)+(q-p).turn_left().turn_to_r(h)));
        v=Line(q,p+((q-p).turn_to_r(l)+(q-p).turn_right().turn_to_r(h)));
        return 2;
    }

    //求两圆相交的面积
    double area_circle(circle v)
    {
        int rel=rel_of_circle(v);
        if(rel>=4) return 0.0;
        if(rel<=2) return min(area(),v.area());
        double d=p.dis(v.p);
        double hf=(r+v.r+d)/2.0;
        double ss=2*sqrt(hf*(hf-r)*(hf-v.r)*(hf-d));
        double a1=acos((r*r+d*d-v.r*v.r)/(2.0*r*d));
        a1=a1*r*r;
        double a2=acos((v.r*v.r+d*d-r*r)/(2.0*v.r*d));
        a2=a2*v.r*v.r;
        return a1+a2-ss;
    }

    //求圆和三角形 pab 的相交面积
    double area_triangle(Point a,Point b)
    {
        if(sgn((p-a)^(p-b))==0) return 0.0;
        Point q[10];
        int len=0;
        q[len++]=a;
        Line l(a,b);
        if(point_line_circle(l,q[1],q[2])==2)
        {
            if(sgn((a-q[1])*(b-q[1]))<0) q[len++]=q[1];
            if(sgn((a-q[2])*(b-q[2]))<0) q[len++]=q[2];
        }
        q[len++]=b;
        if(len==4&&sgn((q[0]-q[1])*(q[2]-q[1]))>0) swap(q[1],q[2]);
        double res=0;
        for(int i=0;i<len-1;i++)
        {
            if(rel_of_point(q[i])==0||rel_of_point(q[i+1])==0)
            {
                double arg=p.rad(q[i],q[i+1]);
                res+=r*r*arg/2.0;
            }
            else res+=abs((q[i]-p)^(q[i+1]-p))/2.0;
        }
        return res;
    }

};

//****************************************************************
//****************************************************************

struct polygon
{
    int n;
    Point p[maxp];
    Line l[maxp];

    void input(int nn)
    {
        n=nn;
        for(int i=0;i<n;i++)
            p[i].input();
    }

    void add(Point q)
    {
        p[n++]=q;
    }

    void getline(void)
    {
        for(int i=0;i<n;i++)
            l[i]=Line(p[i],p[(i+1)%n]);
    }

    struct cmp
    {
        Point p;
        cmp(const Point &p0) { p=p0;}
        bool operator()(const Point &aa,const Point &bb)
        {
            Point a=aa,b=bb;
            int d=sgn((a-p)^(b-p));
            if(d==0)
                return sgn(a.dis(p)-b.dis(p))<0;
            return d>0;
        }
    };

    //进行极角排序
    //首先需要找到最左下角的点
    //需要重载号好 Point 的 < 操作符 (min 函数要用)
    void norm(void)
    {
        Point mi=p[0];
        for(int i=1;i<n;i++) mi=min(mi,p[i]);
        sort(p,p+n,cmp(mi));
    }

    //得到凸包
    //得到的凸包里面的点编号是 0∼n-1 的
    //两种凸包的方法
    //注意如果有影响，要特判下所有点共点，或者共线的特殊情况
    void get_convex(polygon &convex)
    {
        sort(p,p+n);
        convex.n=n;
        for(int i=0;i<min(n,2);i++)
            convex.p[i]=p[i];
        if(convex.n==2&&(convex.p[0]==convex.p[1])) convex.n--;
        if(n<=2) return ;
        int &top=convex.n;
        top=1;
        for(int i=2;i<n;i++)
        {
            while(top&&sgn((convex.p[top]-p[i])^(convex.p[top-1]-p[i]))<=0)
                top--;
            convex.p[++top]=p[i];
        }
        int temp=top;
        convex.p[++top]=p[n-2];
        for(int i=n-3;i>=0;i--)
        {
            while(top!=temp&&sgn((convex.p[top]-p[i])^(convex.p[top-1]-p[i]))<=0)
                top--;
            convex.p[++top]=p[i];
        }
        if(convex.n==2&&(convex.p[0]==convex.p[1])) convex.n--;
        convex.norm();//原来得到的是顺时针的点，排序后逆时针

    }

    //得到凸包的另外一种方法
    void get_convex_graham(polygon &convex)
    {
        norm();
        int &top=convex.n;
        top=0;
        if(n==1)
        {
            top=1;
            convex.p[0]=p[0];
            return ;
        }
        if(n==2)
        {
            top=2;
            convex.p[0]=p[0];
            convex.p[1]=p[1];
            if(convex.p[0]==convex.p[1]) top--;
            return ;
        }

        convex.p[0]=p[0];
        convex.p[1]=p[1];
        top=2;
        for(int i=2;i<n;i++)
        {
            while(top>1&&sgn((convex.p[top-1]-convex.p[top-2])^(p[i]-convex.p[top-2]))<=0)
                top--;
            convex.p[top++]=p[i];
        }
        if(convex.n==2&&(convex.p[0]==convex.p[1])) convex.n--;
    }

    //判断是不是凸的
    bool is_convex(void)
    {
        bool s[8];
        memset(s,false,sizeof(s));
        for(int i=0;i<n;i++)
        {
            int j=(i+1)%n;
            int k=(j+1)%n;
            s[sgn((p[j]-p[i])^(p[k]-p[i]))+1]=true;
            if(s[0]&&s[2]) return false;
        }
        return true;
    }

    //判断点和任意多边形的关系
    // 3 点上
    // 2 边上
    // 1 内部
    // 0 外部
    int rel_of_point(Point q)
    {
        for(int i=0;i<n;i++)
            if(p[i]==q) return 3;
        getline();
        for(int i=0;i<n;i++)
            if(l[i].p_is_on_seg(q)) return 2;
        int cnt=0;
        for(int i=0;i<n;i++)
        {
            int j=(i+1)%n;
            int k=sgn((q-p[j])^(p[i]-p[j]));
            int u=sgn(p[i].y-q.y);
            int v=sgn(p[j].y-q.y);
            if(k>0&&u<0&&v>=0) cnt++;
            if(k<0&&v<0&&u>=0) cnt--;
        }
        return cnt!=0;
    }

    //直线 u 切割凸多边形左侧
    //注意直线方向
    void convex_cut_line(Line u,polygon &po)
    {
        int &top=po.n;
        top=0;
        for(int i=0;i<n;i++)
        {
            int d1=sgn((u.e-u.s)^(p[i]-u.s));
            int d2=sgn((u.e-u.s)^(p[(i+1)%n]-u.s));
            if(d1>=0) po.p[top++]=p[i];
            if(d1*d2<0) po.p[top++]=u.cross_point(Line(p[i],p[(i+1)%n]));
        }
    }

    //得到周长
    double get_cir(void)
    {
        double sum=0;
        for(int i=0;i<n;i++)
            sum+=p[i].dis(p[(i+1)%n]);
        return sum;
    }

    //得到面积
    double get_area(void)
    {
        double sum=0;
        for(int i=0;i<n;i++)
            sum+=(p[i]^p[(i+1)%n]);
        return abs(sum)/2;
    }

    //得到方向
    //1 逆时针
    //2顺时针
    bool get_dir(void)
    {
        double sum=0;
        for(int i=0;i<n;i++)
            sum+=(p[i]^p[(i+1)%n]);
        if(sgn(sum)>0) return 1;
        return 0;
    }

    //得到重心
    Point get_bary_centre(void)
    {
        Point ret(0,0);
        double area=0.0;
        for(int i=1;i<n-1;i++)
        {
            double tmp=(p[i]-p[0])^(p[i+1]-p[0]);
            if(sgn(tmp)==0) continue;
            area+=tmp;
            ret.x+=(p[0].x+p[i].x+p[i+1].x)/3*tmp;
            ret.y+=(p[0].y+p[i].y+p[i+1].y)/3*tmp;
        }
        if(sgn(area)) ret=ret/area;
        return ret;
    }

    //多边形和圆交的面积
    double area_circle(circle c)
    {
        double ans=0;
        for(int i=0;i<n;i++)
        {
            int j=(i+1)%n;
            if(sgn((p[j]-c.p)^(p[i]-c.p))>=0)
                ans+=c.area_triangle(p[i],p[j]);
            else ans-=c.area_triangle(p[i],p[j]);
        }
        return abs(ans);
    }

    //多边形和圆关系
    // 2 圆完全在多边形内
    // 1 圆在多边形里面，碰到了多边形边界
    // 0 其它
    int rel_of_circle(circle c)
    {
        getline();
        int x=2;
        if(rel_of_point(c.p)!=1) return 0;
        for(int i=0;i<n;i++)
        {
            if(c.rel_of_seg(l[i])==2) return 0;
            if(c.rel_of_seg(l[i])==1) x=1;
        }
        return x;
    }
    void random(void)
    {
        srand(19981031);
        for(int i=n-1;i>0;i--)
            swap(p[i],p[rand()%i]);
    }
    //最小圆覆盖
    circle smallest_circle(void)
    {
        random();
        circle cir(Point(0,0),0.0);
        for(int i=0;i<n;i++)
        {
            if(cir.rel_of_point(p[i])>0) continue;
            //如果不在，那么第i个点一定在前i个点的最小覆盖圆上，
            //接着确定前i−1个点中还有哪两个在最小覆盖圆上。
            //因此，设当前圆心为Pi，半径为0，做固定了第i个点的
            //前i个点的最小圆覆盖。
            cir=circle(p[i],0.0);
            for(int j=0;j<i;j++)
            {
                if(cir.rel_of_point(p[j])>0) continue;
                //固定了一个点--去找第二个点：
                //不停地在范围内找到第一个不在当前最小圆上的点Pj ，
                //当前圆心为(Pi+Pj)/2半径为1/2 | Pi Pj | 做固定了两个点的，
                //前 j 个点外加第 i 个点的最小圆覆盖。
                cir=circle((p[i]+p[j])/2,p[j].dis((p[i]+p[j])/2));
                for(int k=0;k<j;k++)
                {
                    if(cir.rel_of_point(p[k])>0) continue;
                    //固定了两个点--去找第三个点：
                    //不停地在范围内找到第一个不在当前最小圆上的点Pk，
                    //当前圆为Pi , Pj , Pk 的外接圆。
                    cir=circle(p[i],p[j],p[k]);
                }

            }
        }
        return cir;
    }

};



int main()
{
    polygon pp;
    int n;
    scanf("%d",&n);
    pp.input(n);
    circle cir=pp.smallest_circle();
    printf("%.10f\n%.10f %.10f\n",cir.r,cir.p.x,cir.p.y);
    return 0;
}