1 // 二分+最短路 uvalive 3270 Simplified GSM Network(推荐) 2 // 题意:已知B(1≤B≤50)个信号站和C(1≤C≤50)座城市的坐标,坐标的绝对值不大于1000,每个城市使用最近的信号站。给定R(1≤R≤250)条连接城市线路的描述和Q(1≤Q≤10)个查询,求相应两城市间通信时最少需要转换信号站的次数。 3 // 思路:建议先阅读 NOI论文 <<计算几何中的二分思想>> 4 // 直接献上题解吧: 5 // 二分! 6 // l的两端点所属信号站相同:w[l]=0。 7 // 否则若|l|<e(蓝):w[l]=1。 8 // 否则,将线段l沿中点(红)分开: 9 // l=l1+l2,w[l]=w[l1]+w[l2]。 10 // 对l1与l2进行同样操作。 11 // 详细请看论文 12 13 #include <iostream> 14 #include <algorithm> 15 #include <cstring> 16 #include <cstdio> 17 #include <vector> 18 #include <cmath> 19 #include <map> 20 #include <queue> 21 using namespace std; 22 #define LL long long 23 typedef pair<int,int> pii; 24 const int inf = 0x3f3f3f3f; 25 const int MOD = 998244353; 26 const int N = 1020; 27 const int maxx = 200010; 28 #define clc(a,b) memset(a,b,sizeof(a)) 29 const double eps = 1e-8; 30 void fre() {freopen("in.txt","r",stdin);} 31 void freout() {freopen("out.txt","w",stdout);} 32 inline int read() {int x=0,f=1;char ch=getchar();while(ch>'9'||ch<'0') {if(ch=='-') f=-1; ch=getchar();}while(ch>='0'&&ch<='9') {x=x*10+ch-'0';ch=getchar();}return x*f;} 33 struct Point{ 34 double x,y; 35 Point(){} 36 Point(double _x,double _y){ 37 x = _x;y = _y; 38 } 39 Point operator -(const Point &b)const{ 40 return Point(x - b.x,y - b.y); 41 } 42 double operator ^(const Point &b)const{ 43 return x*b.y - y*b.x; 44 } 45 double operator *(const Point &b)const{ 46 return x*b.x + y*b.y; 47 } 48 }b[55],c[55]; 49 int B,C,n,q; 50 51 struct node{ 52 int v,c; 53 node(int vv,int cc){ 54 v=vv; 55 c=cc; 56 } 57 node(){} 58 bool operator <(const node &r) const{ 59 return c>r.c; 60 } 61 }; 62 63 struct edge{ 64 int v,cost; 65 edge(int vv=0,int ccost =0):v(vv),cost(ccost){} 66 }; 67 68 vector<edge>e[N]; 69 bool vis[N]; 70 int dist[N]; 71 void dij(int start){ 72 clc(vis,false); 73 for(int i=0;i<=n+1;i++) dist[i]=inf; 74 priority_queue<node>q; 75 while(!q.empty()) q.pop(); 76 dist[start]=0; 77 q.push(node(start,0)); 78 node tmp; 79 while(!q.empty()){ 80 tmp=q.top(); 81 q.pop(); 82 int u=tmp.v; 83 if(vis[u]) continue; 84 vis[u]=true; 85 for(int i=0;i<e[u].size();i++){ 86 int v=e[u][i].v; 87 int cost=e[u][i].cost; 88 if(!vis[v]&&dist[v]>dist[u]+cost){ 89 dist[v]=dist[u]+cost; 90 q.push(node(v,dist[v])); 91 } 92 } 93 } 94 } 95 void add(int u,int v,int w){ 96 e[u].push_back(edge(v,w)); 97 } 98 99 double dis(Point a,Point b){ 100 return sqrt((a-b)*(a-b)); 101 } 102 103 int belong(Point a){ 104 double len=(double)inf; 105 int num; 106 for(int i=1;i<=B;i++){ 107 if(dis(a,b[i])<len){ 108 len=dis(a,b[i]),num=i; 109 } 110 } 111 return num; 112 } 113 114 Point getmid(Point a,Point b){ 115 return Point((a.x+b.x)/2,(a.y+b.y)/2); 116 } 117 118 int calc(Point a,Point b){ 119 if(belong(a)==belong(b)) return 0; 120 if(dis(a,b)<1e-6) return 1; 121 else return calc(a,getmid(a,b))+calc(getmid(a,b),b); 122 } 123 124 int main(){ 125 // fre(); 126 int cas=1; 127 while(~scanf("%d%d%d%d",&B,&C,&n,&q),B,C,n,q){ 128 for(int i=0;i<=1010;i++) e[i].clear(); 129 for(int i=1;i<=B;i++){ 130 scanf("%lf%lf",&b[i].x,&b[i].y); 131 } 132 for(int i=1;i<=C;i++){ 133 scanf("%lf%lf",&c[i].x,&c[i].y); 134 } 135 for(int i=1;i<=n;i++){ 136 int u,v; 137 scanf("%d%d",&u,&v); 138 add(u,v,calc(c[u],c[v])); 139 add(v,u,calc(c[v],c[u])); 140 } 141 printf("Case %d: ",cas++); 142 while(q--){ 143 int u,v; 144 scanf("%d%d",&u,&v); 145 dij(u); 146 if(dist[v]>=inf) printf("Impossible "); 147 else printf("%d ",dist[v]); 148 } 149 } 150 return 0; 151 }