//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 Rd register LD",
            "#define Re register int",
            "using namespace std;",
            "const int N=50003;",
            "const LD eps=1e-8;",
            "inline int dcmp(Rd a){return a<-eps?-1:(a>eps?1:0);}",
            "struct Point{",
            "    LD x,y;Point(LD X=0,LD Y=0){x=X,y=Y;}",
            "    inline void in(){scanf(\"%lf%lf\",&x,&y);}",
            "}cp[N],Poi[N];",
            "inline LD Dot(Vector a,Vector b){return a.x*b.x+a.y*b.y;}",
            "inline LD Cro(Vector a,Vector b){return a.x*b.y-a.y*b.x;}",
            "inline LD Len(Vector a){return Dot(a,a);}",
            "inline Vector operator-(Point a,Point b){return Vector(a.x-b.x,a.y-b.y);}",
            "inline bool cmp(Point a,Point b){return a.x!=b.x?a.x<b.x:a.y<b.y;}",
            "inline int ConvexHull(Point *P,Re n,Point *cp){",
            "\tsort(P+1,P+n+1,cmp);",
            "\tRe t=0;",
            "\tfor(Re i=1;i<=n;++i){",
            "\t\twhile(t>1&&dcmp(Cro(cp[t]-cp[t-1],P[i]-cp[t-1]))<=0)--t;",
            "\t\tcp[++t]=P[i];",
            "\t}",
            "\tRe St=t;",
            "\tfor(Re i=n-1;i>=1;--i){",
            "\t\twhile(t>St&&dcmp(Cro(cp[t]-cp[t-1],P[i]-cp[t-1]))<=0)--t;",
            "\t\tcp[++t]=P[i];",
            "\t}",
            "\treturn --t;",
            "}",
            "int n;",
            "int main(){",
            "//\tfreopen(\"123.txt\",\"r\",stdin);",
            "\tscanf(\"%d\",&n);",
            "\tfor(Re i=1;i<=n;++i)Poi[i].in();",
            "\tRe cnt=ConvexHull(Poi,n,cp);",
            "\tRd Ans=Len(cp[2]-cp[1]);",
            "\tfor(Re i=1,j=3;i<=cnt;++i){",
            "\t\twhile(dcmp(Cro(cp[i+1]-cp[i],cp[j]-cp[i])-Cro(cp[i+1]-cp[i],cp[j+1]-cp[i]))<0)j=j<cnt?j+1:1;",
            "\t\tAns=max(Ans,max(Len(cp[j]-cp[i]),Len(cp[j]-cp[i+1])));",
            "\t}",
            "\tprintf(\"%lld\\n\",(LL)(Ans+0.5));",
            "}",
            ""
        ],
        "description": "插入 旋转卡壳"
    }
}