【JZOJ3297】【SDOI2013】逃考(escape)

2019-11-06 06:05:21

字体：大中小

来源：转载

供稿：网友

Mission

高考又来了，对于不认真读书的来讲真不是个好消息。为了小杨能在家里认真读书，他的亲戚决定驻扎在他的家里监督他学习，有爷爷奶奶、外公外婆、大舅、大嫂、阿姨…… 小杨实在是忍无可忍了，这种生活跟监狱有什么区别！为了他亲爱的小红，为了他的dota，他决定越狱！假设小杨的家是个n*m 的矩阵，左下角坐标为（0，0），右上角坐标为（x1，y1）。小杨有n 个亲戚，驻扎在矩阵里（位置不同，且不在矩阵的边上）。小杨家里的每个地方都被亲戚监控着，而且只被距离最近的亲戚监控：也就是说假设小杨所在的位置是（3,3），亲戚A 在（3,0），A 距离小杨距离是3；亲戚B 在（6,7），则B 距离小杨距离是5。距离A < 距离B，所以（3,3）位置由A 监控。如果“最近距离”出现同时有几个亲戚，那么那个位置同时被那几个亲戚监控。给出小杨的坐标（x0,y0）。因为被发现的人数越少，越狱成功的机会越大，所以小杨需要你设计一条越狱路线到达矩形的边上，且被发现的人数最少。 Ps：小杨做的方向是任意的，也就是说路线上的任意位置只需要是实数。保证一开始小杨只被一个亲戚监控着。 n<=600 $n<=600$

Solution

显然，每个点与其他点连线的中垂线形成的半平面求交，就是这个点的监视范围。然后最短路即可。

Code

#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;}