BZOJ3199:[Sdoi2013]escape 半平面交+最短路

思路:

显然我们的第一想法就是求出每个亲戚控制的区域,那么也就是说这个区域要保证区域内的点到这个亲戚的距离比到其他亲戚的距离都要小.我们发现分界线就是两个亲戚连成的线段的垂直平分线,这样对于每个亲戚有\(n\)个限制(不要忘了矩形区域的四个边界),进行\(n\)次半平面交,即可在\(O(n^2logn)\)的时间内求出所有亲戚控制的区域.

接下来我们暴力枚举出起点在哪个区域,即可建图做最短路.

如何建图?若两个区域存在公共点那么就互相可达.同时我们对每一个区域拆点,这样就建完了图.(其实我是暴力建图的)

最后SPFA水过就好了.

(如果确定自己写的对,实在不知道哪里有问题要抓狂了就看一下这里 有一组数据n=0 233333...)

#include<cstdio>
#include<cstring>
#include<cctype>
#include<iostream>
#include<algorithm>
#include<cmath>
#include<queue>
using namespace std;
 
#define N 610
 
#define eps 1e-8
 
typedef double f2;
struct Point{
    f2 x,y;
    Point(){}
    Point(const f2 _x,const f2 _y):x(_x),y(_y){}
    Point operator+(const Point&B)const{return Point(x+B.x,y+B.y);}
    Point operator-(const Point&B)const{return Point(B.x-x,B.y-y);}
    Point operator*(const f2&p)const{return Point(p*x,p*y);}
}ins[N];
f2 cross(const Point&A,const Point&B){return A.x*B.y-A.y*B.x;}
f2 sqr(const f2&x){return x*x;}
f2 dis(const Point&A,const Point&B){return sqrt(sqr(A.x-B.x)+sqr(A.y-B.y));}
struct Line{
    Point p,v;
    f2 Ang;
    Line(){}
    Line(Point _p,Point _v):p(_p),v(_v){Ang=atan2(_v.y,_v.x);}
    bool operator<(const Line&B)const{return Ang<B.Ang;}
}L[N];int id;
inline Line GetLine(const Point&A,const Point&B){
    Line NewLine;
    NewLine.p=Point((A.x+B.x)/2,(A.y+B.y)/2);
    Point v=A-B;
    NewLine.v=Point(-v.y,v.x);
    NewLine.Ang=atan2(NewLine.v.y,NewLine.v.x);
    return NewLine;
}
inline Point GetLineIntersection(const Line&L1,const Line&L2){
    return L1.p+L1.v*(cross(L1.p-L2.p,L2.v)/cross(L1.v,L2.v));
}
inline bool Onleft(const Line&L,const Point&p){
    return cross(L.v,L.p-p)>=0;
}
Point P[N][N];int siz[N];
inline int GetHalfPlaneIntersection(Line L[],int n,int lab){
    sort(L,L+n);
    Point p[N];
    Line q[N];
    int fr=1,ta=1;q[1]=L[0];
    for(int i=1;i<n;++i){
        while(fr^ta&&!Onleft(L[i],p[ta-1]))--ta;
        while(fr^ta&&!Onleft(L[i],p[fr]))++fr;
        q[++ta]=L[i];
        if(fabs(cross(q[ta].v,q[ta-1].v))<=eps){
            --ta;
            if(!Onleft(L[i],q[ta].p))q[ta]=L[i];
        }
        if(fr^ta)p[ta-1]=GetLineIntersection(q[ta],q[ta-1]);
    }
    while(fr^ta&&!Onleft(q[fr],p[ta-1]))--ta;
    if(ta-fr<=1)return 0;
    p[ta]=GetLineIntersection(q[fr],q[ta]);
    int m=0;
    for(int i=fr;i<=ta;++i)P[lab][m++]=p[i];
    return m;
}
inline bool InPolygen(int lab,Point p){
    for(int i=0;i<siz[lab];++i)if(!Onleft(Line(P[lab][i],P[lab][i]-P[lab][(i+1)%siz[lab]]),p))return 0;
    return 1;
}
 
int head[N*2],next[N*N<<1],end[N*N<<1],len[N*N<<1],ind;
inline void Reset(){ind=0;memset(head,-1,sizeof head);}
inline void addedge(int a,int b,int x){int q=ind++;end[q]=b,next[q]=head[a],head[a]=q,len[q++]=x;}
 
int dist[N*2];bool inq[N*2];queue<int>q;
int spfa(int S,int T){
    memset(dist,0x3f,sizeof dist),dist[S]=0;memset(inq,0,sizeof inq),inq[S]=1,q.push(S);
    int i,j;
    while(!q.empty()){
        i=q.front();q.pop();inq[i]=0;
        for(j=head[i];j!=-1;j=next[j]){
            if(dist[end[j]]>dist[i]+len[j]){
                dist[end[j]]=dist[i]+len[j];
                if(!inq[end[j]])inq[end[j]]=1,q.push(end[j]);
            }
        }
    }return dist[T];
}
 
int main(){
    int T;cin>>T;
    while(T--){
        int n;scanf("%d",&n);if(n==0){puts("0");continue;}
        int Maxx,Maxy,nowx,nowy;cin>>Maxx>>Maxy>>nowx>>nowy;
        register int i,j,k,p;
        for(i=1;i<=n;++i)cin>>ins[i].x>>ins[i].y;
        for(i=1;i<=n;++i){
            id=0;
            L[id++]=Line(Point(0,0),Point(1,0));
            L[id++]=Line(Point(Maxx,0),Point(0,1));
            L[id++]=Line(Point(Maxx,Maxy),Point(-1,0));
            L[id++]=Line(Point(0,Maxy),Point(0,-1));
            for(j=1;j<=n;++j)if(j!=i)L[id++]=GetLine(ins[i],ins[j]);
            siz[i]=GetHalfPlaneIntersection(L,id,i);
        }
         
        //findins
        int begin;
        for(i=1;i<=n;++i)if(siz[i]&&InPolygen(i,Point(nowx,nowy)))begin=i;
         
        Reset();
        for(i=1;i<=n;++i){
            bool ac=0;
            for(j=0;j<siz[i];++j)
                if(fabs(P[i][j].x-0)<=eps||fabs(P[i][j].x-Maxx)<=eps||fabs(P[i][j].y-0)<=eps||fabs(P[i][j].y-Maxy)<=eps)
                    ac=1;
            if(ac)addedge(2*i,2*n+1,0);
        }
        addedge(0,2*begin-1,0);
        for(i=1;i<=n;++i)addedge(2*i-1,2*i,1);
        for(i=1;i<=n;++i){
            for(j=i+1;j<=n;++j){
                bool ac=0;
                for(k=0;k<siz[i]&&!ac;++k)
                    for(p=0;p<siz[j]&&!ac;++p)
                        if(dis(P[i][k],P[j][p])<=eps)ac=1;
                if(ac)addedge(2*i,2*j-1,0),addedge(2*j,2*i-1,0);
            }
        }
         
        printf("%d\n",spfa(0,2*n+1));
    }
     
    return 0;
}