题目链接: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; }