Mobile phones have changed our lifestyle dramatically in the last decade. Mobile phones have a variety of protocols
to connect with one another. One of the most popular networks for mobile phones is the GSM (Global System for
Mobile Communication) network.
In a typical GSM network, a mobile phone connects with the nearest BTS (Base Transceiver Station). A BSC (Base
Station Center) controls several BTSs. Several BSCs are controlled by one MSC (Mobile Services Switching
Center), and this MSC maintains a connection with several other MSCs, a PSTN (Public Switched Telecom
Network) and an ISDN (Integrated Services Digital Network).
This problem uses a simplified model of the conventional GSM network. Our simplified network is composed of up
to fifty BTS towers. When in use, a mobile phone always connects to its nearest BTS tower. The area covered by a
single BTS tower is called a cell. When an active mobile phone is in motion, as it crosses cell boundaries it must
seamlessly switch from one BTS to another. Given the description of a map consisting of cities, roads and BTS
towers, you must determine the minimum number of BTS switches required to go from one city to another.
Figure: Cities here are represented by squares and BTS towers by trapezoids.
Solid lines are roads. The dotted lines show 9 different cells. The minimum
number of switches required to go from city 1 to city 6 is (2+1+0)=3. Note
that city 7 is isolated and cannot be reached.
Each tower and each city location is to be considered as a single point in a two-dimensional Cartesian coordinate
system. If there is a road between two cities, assume that the road is a straight line segment connecting these two
cities. For example, in the figure, traveling on the road from city 1 to city 2 will cross two cell boundaries and thus
requires two switches. Traveling from city 2 to city 5 crosses one cell boundary and traveling from city 5 to city 6
requires no switch. Traveling this route from city 1 to city 6 requires three total switches. Note than any other path
from city 1 to city 6 requires more than three switches. If there is more than one possible way to get from one city to
another, your program must find the optimal route.
The input file contains several test cases. The first line of each test case contains four integers:
B(1
B50),
the number of BTS towers;
C(1C50), the number of cities;
R(0R250), the number of roads;
and
Q(1Q10), the number of queries. Each of the next B lines contains two floating-point numbers x and y,
the Cartesian coordinates of a BTS tower. Each of the next C lines contains two floating-point numbers xi, yi
that indicate the Cartesian coordinates of the ith city
(1iC). Each of the next R lines contains two
integers m and n
(1m, nC), which indicate that there is a road between the m-th and the n-th city.
Each of the next Q lines contains two integers s and d
(1s, dC), the source and destination cities.
No coordinate will have an absolute value greater than 1000. No two towers will be at the same location. No two
cities will be at the same location, and no city will lie on a cell boundary. No road will be coincident with a cell
boundary, nor contain a point lying on the boundary of three or more cells.
The input will end with a line containing four zeros.
For each input set, you should produce Q + 1 lines of output, as shown below. The first line should contain the
number of the test case. Q lines should follow, one for each query, each containing an integer indicating the
minimum number of switches required to go from city s to city d. If it is not possible to go from city s to city d,
print the line `Impossible' instead.
9 7 6 2
5 5
15 5
25 5
5 15
15 15
25 15
5 25
15 25
25 25
8 2
22 3
8 12
18 18
22 12
28 16
28 8
1 2
1 3
2 5
3 4
4 5
5 6
1 6
1 7
0 0 0 0
Case 1:
3
Impossible
題目描述：
行動手機會找尋最接近服務台連線，因此在移動時，可能會將連線轉移到另一個更近的服務台。
給定服務台位置，以及可能的移動路線，計算最少交換連線的次數抵達目的地。
題目解法：
對於一個路徑線段要找到其中有多少交換次數，得到所有路徑的權重後，做一次最短路即可。
採用遞迴求這個線段的權重，如果兩端點都坐落於同一個服務台，那麼中間那一段必然不會有交換的可能。
畫兩個圓便能明白，兩端點分別連向同一個服務台，而這兩個半徑以端點當圓心畫圓。
如果要存在中間一段屬於別的服務台，必然這個服務台會在兩個圓內，與當時假設矛盾，因此不可能。
#include <stdio.h>
#include <math.h>
#include <algorithm>
#define eps 1e-8
using namespace std;
double Bx[55], By[55], Cx[55], Cy[55];
int B, C, R, Q;
double lenV(double lx, double ly, double rx, double ry) {
return (lx-rx)*(lx-rx)+(ly-ry)*(ly-ry);
}
int findConnect(double x, double y) {
static int i, ret = 0;
static double mn, t;
mn = 1e+30;
for(i = 0; i < B; i++) {
t = lenV(Bx[i], By[i], x, y);
if(t < mn) mn = t, ret = i;
}
return ret;
}
int getWeight(double lx, double ly, double rx, double ry) {
int l, r;
l = findConnect(lx, ly);
r = findConnect(rx, ry);
if(l == r) return 0;
if(lenV(lx, ly, rx, ry) < eps) return 1;
return getWeight(lx, ly, (lx+rx)/2, (ly+ry)/2)+
getWeight((lx+rx)/2, (ly+ry)/2, rx, ry);
}
int main() {
int cases = 0;
int i, j, k, x, y;
while(scanf("%d %d %d %d", &B, &C, &R, &Q) == 4) {
if(B+C+R+Q == 0)
break;
for(i = 0; i < B; i++)
scanf("%lf %lf", &Bx[i], &By[i]);
for(i = 0; i < C; i++)
scanf("%lf %lf", &Cx[i], &Cy[i]);
int g[55][55];
for(i = 0; i < C; i++) {
for(j = 0; j < C; j++)
g[i][j] = 0xfffffff;
g[i][i] = 0;
}
for(i = 0; i < R; i++) {
scanf("%d %d", &x, &y);
x--, y--;
g[x][y] = g[y][x] = getWeight(Cx[x], Cy[x], Cx[y], Cy[y]);
}
for(k = 0; k < C; k++)
for(i = 0; i < C; i++)
for(j = 0;j < C; j++)
g[i][j] = min(g[i][j], g[i][k]+g[k][j]);
printf("Case %d:\n", ++cases);
while(Q--) {
scanf("%d %d", &x, &y);
x--, y--;
if(g[x][y] == 0xfffffff)
puts("Impossible");
else
printf("%d\n", g[x][y]);
}
}
return 0;
}
文章定位：
