C++11(clang++ 3.9) 解法, 执行用时: 374ms, 内存消耗: 616K, 提交时间: 2019-03-16 11:30:11

#include<iostream>
#include<algorithm>
#include<stdio.h>
#include<math.h>
#include<string.h>
#define ll long long
#define db double 
using namespace std;
const char* fin="ex3297.in";
const char* fout="ex3297.out";
const db eps=10e-10;
const int inf=0x7fffffff;
const int maxn=607,maxm=maxn*maxn;

bool equ(db v,db x){return fabs(v-x)<=eps;}
int sgn(db x){return equ(x,0.0)?0:(x<0?-1:1);}

struct P{
    db x,y;
    P(db _x=0,db _y=0){x=_x;y=_y;}
    P operator +(P b){return P(x+b.x,y+b.y);}
    P operator -(P b){return P(x-b.x,y-b.y);}
    P operator *(db b){return P(x*b,y*b);}
    P per(){return P(y,-x);}
    db operator ^(P b){return x*b.y-y*b.x;}
    db arg(){return atan2(y,x);}
    void read(){scanf("%lf",&x);scanf("%lf",&y);}
}a[maxn];

struct L{
    P p,v;
    int id;
    L(){}
    L(P _p,P _v,int _id=0){p=_p;v=_v;id=_id;}
    db arg(){return v.arg();}
    P operator &(L b){return b.p+b.v*((v^(p-b.p))/(v^b.v));}
}b[maxn],c[maxn];
int num;
bool cmp(L a,L b){return a.arg()<b.arg();}

bool in(P p,L l){return sgn((p-l.p)^l.v)>=0;}
P mid(P a,P b){return P((a.x+b.x)/2.0,(a.y+b.y)/2.0);}

int n,t,i,j,k,X,Y,sx,sy,st,tot,head,tail;
int fi[maxn],ne[maxm],la[maxm],va[maxm];
int B[maxn*10],dis[maxn];
bool bz[maxn];
void add_line(int a,int b,int c){
    tot++;
    ne[tot]=fi[a];
    la[tot]=b;
    va[tot]=c;
    fi[a]=tot;
}
void add(int v,int u){
    if (dis[v]>u){
        dis[v]=u;
        if (!bz[v]){
            B[++tail]=v;
            bz[v]=true;
        }
    }
}
void spfa(int v){
    int i,j,k;
    memset(dis,127,sizeof(dis));
    head=tail=0;
    add(v,0);
    while (head++<tail){
        for (k=fi[B[head]];k;k=ne[k])
            add(la[k],dis[B[head]]+va[k]);
        bz[B[head]]=false;
    }
}
int main(){
    scanf("%d",&t);
    while (t--){
        scanf("%d",&n);
        scanf("%d%d%d%d",&X,&Y,&sx,&sy);
        tot=0;
        st=0;
        P stp(sx,sy);
        memset(fi,0,sizeof(fi));
        for (i=1;i<=n;i++) a[i].read();
        for (i=1;i<=n;i++){
            num=0;
            for (j=1;j<=n;j++){
                if (i==j) continue;
                b[++num]=L(mid(a[i],a[j]),(a[j]-a[i]).per(),j);
            }
            b[++num]=L(P(0,0),P(0,1),0);
            b[++num]=L(P(0,Y),P(1,0),0);
            b[++num]=L(P(X,Y),P(0,-1),0);
            b[++num]=L(P(X,0),P(-1,0),0);
            sort(b+1,b+num+1,cmp);
            int N=0;
            for (j=1;j<=num;j++){
                if (!N) b[++N]=b[j];
                else if (!equ(b[N].arg(),b[j].arg())) b[++N]=b[j];
                else if (in(b[j].p,b[N])) b[N]=b[j];
            }
            num=N;
            int head=1,tail=2;
            bool noans=false;
            c[1]=b[1],c[2]=b[2];
            for (j=3;j<=num;j++){
                while (head<tail && !in(c[tail]&c[tail-1],b[j])) tail--;
                while (head<tail && !in(c[head]&c[head+1],b[j])) head++;
                if (head==tail && sgn(c[head].v^b[j].v)<=0){noans=true;break;}
                c[++tail]=b[j];
            }
            if (noans) continue;
            while (head<tail && !in(c[tail]&c[tail-1],c[head])) tail--;
            for (j=head;j<=tail;j++) add_line(i,c[j].id,1);
            if (!st){
                bool ST=true;
                for (j=head;j<=tail;j++)
                    if (!in(stp,c[j])){
                        ST=false;
                        break;
                    }
                if (ST) st=i;
            }
        }
        spfa(st);
        printf("%d\n",dis[0]);
    }
    return 0;
}