//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<cstring>",
            "#include<cstdio>",
            "#include<cmath>",
            "#include<queue>",
            "#define LD double",
            "#define LL long long",
            "#define Vector Point",
            "#define Re register int",
            "using namespace std;",
            "const int N=610;",
            "const LD eps=1e-8,Pi=acos(-1);",
            "inline int dcmp(LD a){return a<-eps?-1:(a>eps?1:0);}",
            "struct Point{",
            "\tLD x,y;Point(LD X=0,LD Y=0){x=X,y=Y;}",
            "\tinline void in(){scanf(\"%lf%lf\",&x,&y);}",
            "\tinline void print(){printf(\"%.2lf %.2lf\\n\",x,y);}",
            "}P[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+(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 x){return Vector(a.x*x,a.y*x);}",
            "inline Point cross(Point a,Point b,Point c,Point d){",
            "\tVector x=b-a,y=d-c,z=a-c;",
            "\treturn a+x*(Cro(y,z)/Cro(x,y));",
            "}",
            "inline int judge(Point a,Point L,Point R){",
            "\treturn dcmp(Cro(L-a,R-a))>0;",
            "}",
            "struct Line{",
            "\tPoint a,b;LD k;int id;Line(Point A=Point(0,0),Point B=Point(0,0)){id=0,a=A,b=B,k=atan2(b.y-a.y,b.x-a.x);}",
            "\tinline bool operator<(const Line &O)const{return dcmp(k-O.k)?dcmp(k-O.k)<0:judge(O.a,O.b,b);}",
            "}Q[N];",
            "inline Point cross(Line L1,Line L2){return cross(L1.a,L1.b,L2.a,L2.b);}",
            "inline int judge(Line L,Point a){return dcmp(Cro(a-L.a,L.b-L.a))>0;}",
            "inline void halfcut(Line *L,Re &n){",
            "\tsort(L+1,L+n+1);Re m=n;n=0;",
            "\tfor(Re i=1;i<=m;++i)if(i==1||dcmp(L[i].k-L[i-1].k))L[++n]=L[i];",
            "\tRe h=1,t=0;",
            "\tfor(Re i=1;i<=n;++i){",
            "\t\twhile(h<t&&judge(L[i],cross(Q[t],Q[t-1])))--t;",
            "\t\twhile(h<t&&judge(L[i],cross(Q[h],Q[h+1])))++h;",
            "\t\tQ[++t]=L[i];",
            "\t}",
            "\twhile(h<t&&judge(Q[h],cross(Q[t],Q[t-1])))--t;",
            "\twhile(h<t&&judge(Q[t],cross(Q[h],Q[h+1])))++h;",
            "\tn=0;",
            "\tfor(Re i=h;i<=t;++i)L[++n]=Q[i];",
            "}",
            "inline Point turnP(Point a,LD theta){",
            "\tLD x=a.x*cos(theta)+a.y*sin(theta);",
            "\tLD y=a.y*cos(theta)-a.x*sin(theta);",
            "\treturn Point(x,y);",
            "}",
            "inline Line get_midL(Point a,Point b){",
            "\tPoint M=a+((b-a)*0.5);",
            "\treturn Line(M,M+turnP(a-b,Pi/2.0));",
            "}",
            "int n,m,T,st,ed;Point a,b,c,d,x0,A[N];Line L[N];",
            "struct Dijkstra{",
            "\tint o,dis[N],pan[N],head[N];",
            "\tstruct QAQ{int w,to,next;}a[N*N];",
            "\tinline void add(Re x,Re y,Re z){a[++o].w=z,a[o].to=y,a[o].next=head[x],head[x]=o;}",
            "\tstruct QWQ{int x,d;inline bool operator<(const QWQ &O)const{return d>O.d;}};",
            "\tpriority_queue<QWQ>Q;",
            "\tinline void CL(){memset(head,0,sizeof(head)),o=0;}",
            "\tinline int dijkstra(Re st,Re ed){",
            "\t\tfor(Re i=0;i<=n;++i)dis[i]=2e9,pan[i]=0;",
            "\t\tQ.push((QWQ){st,dis[st]=1});",
            "\t\twhile(!Q.empty()){",
            "\t\t\tRe x=Q.top().x;Q.pop();",
            "\t\t\tif(pan[x])continue;",
            "\t\t\tpan[x]=1;",
            "\t\t\tfor(Re i=head[x],to;i;i=a[i].next)",
            "\t\t\t\tif(dis[to=a[i].to]>dis[x]+a[i].w)",
            "\t\t\t\t\tQ.push((QWQ){to,dis[to]=dis[x]+a[i].w});",
            "\t\t}",
            "\t\treturn dis[ed];",
            "\t}",
            "}T1;",
            "int main(){",
            "//\tfreopen(\"456.txt\",\"r\",stdin);",
            "\tscanf(\"%d\",&T);",
            "\twhile(T--){",
            "\t\tscanf(\"%d\",&n),c.in(),x0.in(),T1.CL();",
            "\t\tif(!n){puts(\"0\");continue;}",
            "\t\ta=Point(0,0),b=Point(c.x,0),d=Point(0,c.y);",
            "\t\tfor(Re i=1;i<=n;++i){",
            "\t\t\tA[i].in();",
            "\t\t\tif(A[i].x>c.x||A[i].y>c.y){--i,--n;continue;}",
            "\t\t\tif(dcmp(Len(A[i]-x0)-Len(A[st]-x0))<0)st=i;",
            "\t\t}",
            "//\t\tprintf(\"st=%d\\n\",st);",
            "\t\tfor(Re i=1;i<=n;++i){",
            "\t\t\tRe m=0;",
            "\t\t\tfor(Re j=1;j<=n;++j)",
            "\t\t\t\tif(i!=j)L[++m]=get_midL(A[i],A[j]),L[m].id=j;",
            "\t\t\tL[++m]=Line(a,b),L[++m]=Line(b,c),L[++m]=Line(c,d),L[++m]=Line(d,a);",
            "\t\t\thalfcut(L,m);",
            "\t\t\tfor(Re j=1;j<=m;++j)T1.add(i,L[j].id,L[j].id>0);",
            "\t\t}",
            "\t\tprintf(\"%d\\n\",T1.dijkstra(st,ed));",
            "\t}",
            "}",
            ""
        ],
        "description": "插入 逃考"
    }
}