首页 > 代码库 > BZOJ 3199 escape

BZOJ 3199 escape

题目链接:http://www.lydsy.com:808/JudgeOnline/problem.php?id=3199

题意:给出n个点。对于平面上任意一点p,p到n个点中的哪个点的距离最近我们就称p就被哪个点控制。有可能p被多个点同时控制(距离相等的时候)。给出一个矩形框(0,0,X,Y)以及框内一点q。从q到达矩形框上的途中,最少被多少个点控制过?

思路:n个点中的每个点有一个控制区域。某个点和其他点中垂线组成的半平面交就是这个区域。这个可以用凸包计算。这里是一个nlogn求凸包的算法,第二次遇到这个算法,第一次是:

http://www.cnblogs.com/jianglangcaijin/archive/2013/03/07/2947784.html

然后就是有公共边的连边求最短路。

point S,p[N];  struct Tline{    point p1,p2;    int id;    double ang;    Tline(){}     Tline(point _p1,point _p2,int _id)    {        p1=_p1;        p2=_p2;        ang=atan2(p2.y-p1.y,p2.x-p1.x);        id=_id;    }}L[N];   point crossPoint(Tline l1,Tline l2){    double ta=(l1.p2-l2.p1)*(l1.p1-l2.p1);    double tb=(l1.p1-l2.p2)*(l1.p2-l2.p2);    return (l2.p1*tb+l2.p2*ta)/(ta+tb);} double xx,yy;int n,tot;  double dist(const point &a){    return sqrt(a.x*a.x+a.y*a.y);} int cmp(const Tline &a,const Tline &b){    if(sgn(a.ang-b.ang)==0) return sgn((a.p1-b.p1)*(b.p2-b.p1))<0;    return sgn(a.ang-b.ang)<0;} int onleft(const Tline &l1,const Tline &l2,const Tline &l3){    point tp=crossPoint(l1,l2);    return sgn((l3.p2-l3.p1)*(tp-l3.p1))>=0;}  vector<int> g[N]; void hpi(int x){    sort(L+1,L+1+tot,cmp);    int i,tp=1;    for(i=2;i<=tot;i++) if(sgn(L[i].ang-L[i-1].ang)!=0) L[++tp]=L[i];    tot=tp;     int front=1,rear=1;    int Q[N];    Q[1]=1;      for(i=2;i<=tot;i++)    {        while(front<rear&&!onleft(L[Q[rear-1]],L[Q[rear]],L[i]))rear--;        while(front<rear&&!onleft(L[Q[front]],L[Q[front+1]],L[i]))front++;        Q[++rear]=i;    }    while(front<rear&&!onleft(L[Q[rear-1]],L[Q[rear]],L[Q[front]]))rear--;    while(front<rear&&!onleft(L[Q[front]],L[Q[front+1]],L[Q[rear]]))front++;     if(rear-front<2)return;    for(i=front;i<=rear;i++)    {        int y=L[Q[i]].id;        g[x].pb(y);    }} void work(int x){    tot=0;    L[++tot]=Tline(point(0,0),  point(xx,0), n+1);    L[++tot]=Tline(point(xx,0), point(xx,yy),n+1);    L[++tot]=Tline(point(xx,yy),point(0,yy), n+1);    L[++tot]=Tline(point(0,yy), point(0,0),  n+1);    int i;    for(i=1;i<=n;i++) if(i!=x)    {        point S=(p[i]+p[x])/2;        point d=(p[i]-p[x]).zhuanNi(PI/2);        point T=S+d;        L[++tot]=Tline(S,T,i);    }    hpi(x);} int bfs(int st){    queue<int> Q;    Q.push(st);     int i,dis[N],visit[N];    for(i=1;i<=n+1;i++) dis[i]=1e9,visit[i]=0;     dis[st]=0;    visit[st]=1;     while(!Q.empty())    {        int u=Q.front();        Q.pop();         for(i=0;i<SZ(g[u]);i++)        {            int v=g[u][i];            if(!visit[v])            {                 visit[v]=1;                dis[v]=dis[u]+1;                Q.push(v);            }        }    }    return dis[n+1];} int main(){    int T=getInt();    while(T--)    {        n=getInt();        xx=getInt(),yy=getInt();        S.get();         int i;        for(i=1;i<=n;i++)p[i].get(),g[i].clear();         for(i=1;i<=n;i++) work(i);          int st=1;        double tmp=dist(p[1]-S);        for(i=2;i<=n;i++) if(dist(p[i]-S)<tmp)        {            tmp=dist(p[i]-S);            st=i;        }        printf("%d\n",bfs(st));    }    return 0;}

 

BZOJ 3199 escape