//Place your snippets for cpp here. Each snippet is defined under a snippet name and has a prefix, body and 
// description. The prefix is what is used to trigger the snippet and the body will be expanded and inserted. Possible variables are:
// $1, $2 for tab stops, $0 for the final cursor position, and ${1:label}, ${2:another} for placeholders. Placeholders with the 
// same ids are connected.
// prefix 的格式要求是 acm-[一级标题编号].[二级标题编号][该代码片段的英文简称]
// description 的格式要求是 "插入 [该代码片段的中文名]"

{
    "最小圆覆盖": {
        "prefix": "acm-8.3随机增量法",
        "body": [
            "#include<algorithm>",
            "#include<cstdio>",
            "#include<cmath>",
            "#define LD double",
            "#define LL long long",
            "#define Vector Point",
            "#define Re register int",
            "#define S(a) ((a)*(a))",
            "using namespace std;",
            "const int N=1e6+3;",
            "const LD eps=1e-8;",
            "inline int dcmp(LD a){return a<-eps?-1:(a>eps?1:0);}// 撤销操作",
            "int n;",
            "struct Point{",
            "    LD x,y;Point(LD X=0,LD Y=0){x=X,y=Y;}",
            "    inline void in(){scanf(\"%lf%lf\",&x,&y);}",
            "}P[N];",
            "inline LD Dot(Vector a,Vector b){return a.x*b.x+a.y*b.y;}",
            "inline LD Len(Vector a){return sqrt(Dot(a,a));}",
            "inline Vector operator+(Vector a,Vector b){return Vector(a.x+b.x,a.y+b.y);}",
            "inline Vector operator-(Vector a,Vector b){return Vector(a.x-b.x,a.y-b.y);}",
            "inline Vector operator*(Vector a,LD b){return Vector(a.x*b,a.y*b);}",
            "struct Circle{Point O;LD r;Circle(Point P,LD R=0){O=P,r=R;}};",
            "inline Circle getcircle(Point A,Point B,Point C){",
            "\tLD x1=A.x,y1=A.y,x2=B.x,y2=B.y,x3=C.x,y3=C.y;",
            "\tLD D=((S(x2)+S(y2)-S(x3)-S(y3))*(y1-y2)-(S(x1)+S(y1)-S(x2)-S(y2))*(y2-y3))/((x1-x2)*(y2-y3)-(x2-x3)*(y1-y2));",
            "\tLD E=(S(x1)+S(y1)-S(x2)-S(y2)+D*(x1-x2))/(y2-y1);",
            "\tLD F=-(S(x1)+S(y1)+D*x1+E*y1);",
            "\treturn Circle(Point(-D/2.0,-E/2.0),sqrt((S(D)+S(E)-4.0*F)/4.0));",
            "}",
            "inline int PIC(Circle &C,Point a){return dcmp(Len(a-C.O)-C.r)<=0;}",
            "inline void Random(){for(Re i=1;i<=n;++i)swap(P[i],P[rand()%n+1]);}",
            "int main(){",
            "//\tfreopen(\"123.txt\",\"r\",stdin);",
            "\tscanf(\"%d\",&n);",
            "\tfor(Re i=1;i<=n;++i)P[i].in();",
            "//\trandom_shuffle(P+1,P+n+1);",
            "\tRandom();Circle C=Circle(P[1],0);",
            "\tfor(Re i=2;i<=n;++i)",
            "\t\tif(!PIC(C,P[i])){",
            "\t\t\tC=Circle(P[i],0);",
            "\t\t\tfor(Re j=1;j<i;++j)",
            "\t\t\t\tif(!PIC(C,P[j])){",
            "\t\t\t\t\tC.O=(P[i]+P[j])*0.5,C.r=Len(P[j]-C.O);",
            "\t\t\t\t\tfor(Re k=1;k<j;++k)if(!PIC(C,P[k]))C=getcircle(P[i],P[j],P[k]);",
            "\t\t\t\t}",
            "\t\t}",
            "\tprintf(\"%.2lf %.2lf %.2lf\\n\",C.O.x,C.O.y,C.r);",
            "}",
            ""
        ],
        "description": "插入 最小圆覆盖"
    }
}