题目描述在简化的GSM\texttt{GSM}GSM网络中移动电话始终连接最近的BTS\texttt{BTS}BTS基站。每个BTS\texttt{BTS}BTS覆盖的区域称为一个小区。当移动电话从一个城市沿道路前往另一个城市时途中跨越小区边界就需要进行一次基站切换。题目给定BBB个BTS\texttt{BTS}BTS塔、CCC个城市、RRR条道路以及QQQ个查询要求计算从源城市sss到目标城市ddd所需的最小切换次数。若无法到达则输出Impossible。输入格式输入包含多组测试数据。每组数据第一行给出四个整数BBB、CCC、RRR、QQQ分别表示BTS\texttt{BTS}BTS塔数量、城市数量、道路数量和查询数量。接下来BBB行每行两个浮点数表示一个BTS\texttt{BTS}BTS塔的坐标。接下来CCC行每行两个浮点数表示一个城市的坐标。接下来RRR行每行两个整数mmm、nnn表示城市mmm与城市nnn之间有一条道路。接下来QQQ行每行两个整数sss、ddd表示一次查询的源城市与目标城市。输入以四个000结束。输出格式对每组测试数据先输出一行Case X:其中XXX为测试数据编号。随后对每个查询输出一行为一个整数表示最少切换次数或输出Impossible。样例输入9 7 6 2 5 5 15 5 25 5 15 15 15 25 15 5 25 15 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题目分析该问题的核心在于计算沿一条道路从城市mmm到城市nnn时需要经过多少个小区边界。每个BTS\texttt{BTS}BTS塔覆盖一个小区小区边界即为到两个最近BTS\texttt{BTS}BTS塔距离相等的点的轨迹也就是Voronoi\texttt{Voronoi}Voronoi图的边。因此一条道路上的切换次数等于这条道路线段所穿过的Voronoi\texttt{Voronoi}Voronoi边数量。直接计算Voronoi\texttt{Voronoi}Voronoi图较为复杂但可以利用一个等价判定方法。对于道路线段上的一点ppp其最近的BTS\texttt{BTS}BTS塔是覆盖ppp的小区所属的塔。如果沿线段从城市mmm移动到城市nnn每当最近的BTS\texttt{BTS}BTS塔发生变化就发生一次切换。因此切换次数等于线段上“最近BTS\texttt{BTS}BTS塔”发生变化的位置数量。一种可行的判定方式是对于每个BTS\texttt{BTS}BTS塔iii判断它是否在线段的某一部分上成为最近的塔。若塔iii在线段上存在一段区间非空使得该区间内所有点到塔iii的距离都不大于到其他塔的距离则塔iii对切换次数有贡献。具体实现时对每个塔iii计算线段上距离塔iii最近的点qiq_iqi即塔iii到线段的投影点若投影落在线段外则取最近的端点。然后检查qiq_iqi是否真的是线段上所有点中到塔iii最近的点。若存在另一个塔jjj使得qiq_iqi到塔jjj的距离小于qiq_iqi到塔iii的距离则塔iii不可能在线段上成为最近的塔不计入贡献。否则塔iii在线段上至少有一个点即qiq_iqi是最近的因此计入一次切换。由于线段上最近的塔会依次变化每经过一个塔的“势力范围”就对应一次切换。相邻两个势力范围之间的边界即为一次切换。若线段上共有kkk个塔的势力范围出现则切换次数为k−1k - 1k−1。代码中getSwitchs(m, n)函数正是按照这一思路实现的它统计线段上成为最近塔的BTS\texttt{BTS}BTS塔数量然后返回该数量减111。得到每条道路的切换次数后问题转化为在一个带权无向图上求两点间的最短路径。由于城市数量C≤50C \le 50C≤50道路数量R≤250R \le 250R≤250可以直接使用Floyd\texttt{Floyd}Floyd算法计算所有城市对之间的最小切换次数。对于每个查询若距离仍为初始的无穷大则输出Impossible否则输出最短距离。解题思路步骤1\texttt{1}1. 读取所有BTS\texttt{BTS}BTS塔坐标、城市坐标、道路信息以及查询信息。步骤2\texttt{2}2. 对于每条道路(m,n)(m, n)(m,n)调用getSwitchs(m, n)计算从城市mmm到城市nnn所需切换次数。该函数遍历每个BTS\texttt{BTS}BTS塔iii计算塔iii到线段mnmnmn的最近点qiq_iqi并检查qiq_iqi是否被其他塔更近地覆盖。若塔iii是qiq_iqi的最近塔则计数加111。最终返回计数减111即为切换次数。步骤3\texttt{3}3. 将每条道路的切换次数作为边权构建距离矩阵DDD。初始化D[i][i]0D[i][i] 0D[i][i]0其余为无穷大。对于每条道路(m,n)(m, n)(m,n)令D[m][n]D[n][m]切换次数D[m][n] D[n][m] \text{切换次数}D[m][n]D[n][m]切换次数。步骤4\texttt{4}4. 使用Floyd\texttt{Floyd}Floyd算法更新距离矩阵对每个中间点kkk若D[i][k]D[k][j]D[i][j]D[i][k] D[k][j] D[i][j]D[i][k]D[k][j]D[i][j]则更新D[i][j]D[i][j]D[i][j]。步骤5\texttt{5}5. 对每个查询(s,d)(s, d)(s,d)若D[s][d]D[s][d]D[s][d]为无穷大输出Impossible否则输出D[s][d]D[s][d]D[s][d]。复杂度分析计算每条道路的切换次数需要遍历BBB个塔并对每个塔检查其他BBB个塔因此单条道路的计算量为O(B2)O(B^2)O(B2)。共有RRR条道路故预处理阶段时间复杂度为O(R⋅B2)O(R \cdot B^2)O(R⋅B2)。Floyd\texttt{Floyd}Floyd算法的时间复杂度为O(C3)O(C^3)O(C3)。空间复杂度为O(C2BR)O(C^2 B R)O(C2BR)主要用于存储距离矩阵和坐标数组。在题目给定的约束下B≤50B \le 50B≤50C≤50C \le 50C≤50R≤250R \le 250R≤250计算量完全可行。代码实现// Simplified GSM Network// UVa ID: 1039// Verdict: Accepted// Submission Date: 2018-12-14// UVa Run Time: 0.000s//// 版权所有C2018邱秋。metaphysis # yeah dot net#includebits/stdc.husingnamespacestd;structpoint{doublex,y;point(doublex0,doubley0):x(x),y(y){}pointoperator(point p){returnpoint(xp.x,yp.y);};pointoperator-(point p){returnpoint(x-p.x,y-p.y);};pointoperator*(doublek){returnpoint(x*k,y*k);};pointoperator/(doublek){returnpoint(x/k,y/k);};};structsegment{point p1,p2;};typedefsegment line;doubledot(point a,point b){returna.x*b.xa.y*b.y;}doublecross(point a,point b){returna.x*b.y-b.x*a.y;}doublenorm(point p){returnp.x*p.xp.y*p.y;};doubleabs(point p){returnsqrt(norm(p));};doublegetDist(point a,point b){returnabs(a-b);}constintINF0x3f3f3f3f;intB,C,R,Q,D[64][64];point towers[64],cities[64];intgetSwitchs(intm,intn){intswitches0;doubled;point nearest;for(inti1;iB;i){// Get distance between a BTS tower and a road.if(dot(cities[n]-cities[m],towers[i]-cities[m])0.0){dgetDist(towers[i],cities[m]);nearestcities[m];}elseif(dot(cities[m]-cities[n],towers[i]-cities[n])0.0){dgetDist(towers[i],cities[n]);nearestcities[n];}else{// Get the project of point on segment.segment s;s.p1cities[m],s.p2cities[n];point bases.p2-s.p1;doublerdot(towers[i]-s.p1,base)/norm(base);nearests.p1base*r;dgetDist(towers[i],nearest);}boolbesttrue;for(intj1;jB;j){if(ij)continue;if(getDist(nearest,towers[j])d){bestfalse;break;}}if(best)switches;}returnswitches-1;}intmain(intargc,char*argv[]){cin.tie(0),cout.tie(0),ios::sync_with_stdio(false);intcases0;while(cinBCRQ){if(B0)break;for(inti1;iB;i)cintowers[i].xtowers[i].y;for(inti1;iC;i)cincities[i].xcities[i].y;memset(D,INF,sizeof(D));for(inti1;iC;i)D[i][i]0;for(inti1,m,n;iR;i){cinmn;D[m][n]D[n][m]getSwitchs(m,n);}for(intk1;kC;k)for(inti1;iC;i)for(intj1;jC;j)D[i][j]min(D[i][j],D[i][k]D[k][j]);coutCase cases:\n;for(inti1,s,d;iQ;i){cinsd;if(D[s][d]INF)coutImpossible;elsecoutD[s][d];cout\n;}}return0;}总结本题的关键在于将“沿道路行驶时的基站切换次数”转化为“道路线段穿过的Voronoi\texttt{Voronoi}Voronoi小区边界数量”。通过计算每个BTS\texttt{BTS}BTS塔到线段的最近点并判断该点是否被其他塔更近地覆盖可以确定该塔是否在线段上形成一段势力范围。统计势力范围的数量并减111即得切换次数。随后使用Floyd\texttt{Floyd}Floyd算法求解带权图上的最短路径即可。需要注意浮点数比较的精度问题代码中采用严格小于号进行判断在题目给定的约束下能够正确工作。
题目描述在简化的GSM\texttt{GSM}GSM网络中移动电话始终连接最近的BTS\texttt{BTS}BTS基站。每个BTS\texttt{BTS}BTS覆盖的区域称为一个小区。当移动电话从一个城市沿道路前往另一个城市时途中跨越小区边界就需要进行一次基站切换。题目给定BBB个BTS\texttt{BTS}BTS塔、CCC个城市、RRR条道路以及QQQ个查询要求计算从源城市sss到目标城市ddd所需的最小切换次数。若无法到达则输出Impossible。输入格式输入包含多组测试数据。每组数据第一行给出四个整数BBB、CCC、RRR、QQQ分别表示BTS\texttt{BTS}BTS塔数量、城市数量、道路数量和查询数量。接下来BBB行每行两个浮点数表示一个BTS\texttt{BTS}BTS塔的坐标。接下来CCC行每行两个浮点数表示一个城市的坐标。接下来RRR行每行两个整数mmm、nnn表示城市mmm与城市nnn之间有一条道路。接下来QQQ行每行两个整数sss、ddd表示一次查询的源城市与目标城市。输入以四个000结束。输出格式对每组测试数据先输出一行Case X:其中XXX为测试数据编号。随后对每个查询输出一行为一个整数表示最少切换次数或输出Impossible。样例输入9 7 6 2 5 5 15 5 25 5 15 15 15 25 15 5 25 15 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题目分析该问题的核心在于计算沿一条道路从城市mmm到城市nnn时需要经过多少个小区边界。每个BTS\texttt{BTS}BTS塔覆盖一个小区小区边界即为到两个最近BTS\texttt{BTS}BTS塔距离相等的点的轨迹也就是Voronoi\texttt{Voronoi}Voronoi图的边。因此一条道路上的切换次数等于这条道路线段所穿过的Voronoi\texttt{Voronoi}Voronoi边数量。直接计算Voronoi\texttt{Voronoi}Voronoi图较为复杂但可以利用一个等价判定方法。对于道路线段上的一点ppp其最近的BTS\texttt{BTS}BTS塔是覆盖ppp的小区所属的塔。如果沿线段从城市mmm移动到城市nnn每当最近的BTS\texttt{BTS}BTS塔发生变化就发生一次切换。因此切换次数等于线段上“最近BTS\texttt{BTS}BTS塔”发生变化的位置数量。一种可行的判定方式是对于每个BTS\texttt{BTS}BTS塔iii判断它是否在线段的某一部分上成为最近的塔。若塔iii在线段上存在一段区间非空使得该区间内所有点到塔iii的距离都不大于到其他塔的距离则塔iii对切换次数有贡献。具体实现时对每个塔iii计算线段上距离塔iii最近的点qiq_iqi即塔iii到线段的投影点若投影落在线段外则取最近的端点。然后检查qiq_iqi是否真的是线段上所有点中到塔iii最近的点。若存在另一个塔jjj使得qiq_iqi到塔jjj的距离小于qiq_iqi到塔iii的距离则塔iii不可能在线段上成为最近的塔不计入贡献。否则塔iii在线段上至少有一个点即qiq_iqi是最近的因此计入一次切换。由于线段上最近的塔会依次变化每经过一个塔的“势力范围”就对应一次切换。相邻两个势力范围之间的边界即为一次切换。若线段上共有kkk个塔的势力范围出现则切换次数为k−1k - 1k−1。代码中getSwitchs(m, n)函数正是按照这一思路实现的它统计线段上成为最近塔的BTS\texttt{BTS}BTS塔数量然后返回该数量减111。得到每条道路的切换次数后问题转化为在一个带权无向图上求两点间的最短路径。由于城市数量C≤50C \le 50C≤50道路数量R≤250R \le 250R≤250可以直接使用Floyd\texttt{Floyd}Floyd算法计算所有城市对之间的最小切换次数。对于每个查询若距离仍为初始的无穷大则输出Impossible否则输出最短距离。解题思路步骤1\texttt{1}1. 读取所有BTS\texttt{BTS}BTS塔坐标、城市坐标、道路信息以及查询信息。步骤2\texttt{2}2. 对于每条道路(m,n)(m, n)(m,n)调用getSwitchs(m, n)计算从城市mmm到城市nnn所需切换次数。该函数遍历每个BTS\texttt{BTS}BTS塔iii计算塔iii到线段mnmnmn的最近点qiq_iqi并检查qiq_iqi是否被其他塔更近地覆盖。若塔iii是qiq_iqi的最近塔则计数加111。最终返回计数减111即为切换次数。步骤3\texttt{3}3. 将每条道路的切换次数作为边权构建距离矩阵DDD。初始化D[i][i]0D[i][i] 0D[i][i]0其余为无穷大。对于每条道路(m,n)(m, n)(m,n)令D[m][n]D[n][m]切换次数D[m][n] D[n][m] \text{切换次数}D[m][n]D[n][m]切换次数。步骤4\texttt{4}4. 使用Floyd\texttt{Floyd}Floyd算法更新距离矩阵对每个中间点kkk若D[i][k]D[k][j]D[i][j]D[i][k] D[k][j] D[i][j]D[i][k]D[k][j]D[i][j]则更新D[i][j]D[i][j]D[i][j]。步骤5\texttt{5}5. 对每个查询(s,d)(s, d)(s,d)若D[s][d]D[s][d]D[s][d]为无穷大输出Impossible否则输出D[s][d]D[s][d]D[s][d]。复杂度分析计算每条道路的切换次数需要遍历BBB个塔并对每个塔检查其他BBB个塔因此单条道路的计算量为O(B2)O(B^2)O(B2)。共有RRR条道路故预处理阶段时间复杂度为O(R⋅B2)O(R \cdot B^2)O(R⋅B2)。Floyd\texttt{Floyd}Floyd算法的时间复杂度为O(C3)O(C^3)O(C3)。空间复杂度为O(C2BR)O(C^2 B R)O(C2BR)主要用于存储距离矩阵和坐标数组。在题目给定的约束下B≤50B \le 50B≤50C≤50C \le 50C≤50R≤250R \le 250R≤250计算量完全可行。代码实现// Simplified GSM Network// UVa ID: 1039// Verdict: Accepted// Submission Date: 2018-12-14// UVa Run Time: 0.000s//// 版权所有C2018邱秋。metaphysis # yeah dot net#includebits/stdc.husingnamespacestd;structpoint{doublex,y;point(doublex0,doubley0):x(x),y(y){}pointoperator(point p){returnpoint(xp.x,yp.y);};pointoperator-(point p){returnpoint(x-p.x,y-p.y);};pointoperator*(doublek){returnpoint(x*k,y*k);};pointoperator/(doublek){returnpoint(x/k,y/k);};};structsegment{point p1,p2;};typedefsegment line;doubledot(point a,point b){returna.x*b.xa.y*b.y;}doublecross(point a,point b){returna.x*b.y-b.x*a.y;}doublenorm(point p){returnp.x*p.xp.y*p.y;};doubleabs(point p){returnsqrt(norm(p));};doublegetDist(point a,point b){returnabs(a-b);}constintINF0x3f3f3f3f;intB,C,R,Q,D[64][64];point towers[64],cities[64];intgetSwitchs(intm,intn){intswitches0;doubled;point nearest;for(inti1;iB;i){// Get distance between a BTS tower and a road.if(dot(cities[n]-cities[m],towers[i]-cities[m])0.0){dgetDist(towers[i],cities[m]);nearestcities[m];}elseif(dot(cities[m]-cities[n],towers[i]-cities[n])0.0){dgetDist(towers[i],cities[n]);nearestcities[n];}else{// Get the project of point on segment.segment s;s.p1cities[m],s.p2cities[n];point bases.p2-s.p1;doublerdot(towers[i]-s.p1,base)/norm(base);nearests.p1base*r;dgetDist(towers[i],nearest);}boolbesttrue;for(intj1;jB;j){if(ij)continue;if(getDist(nearest,towers[j])d){bestfalse;break;}}if(best)switches;}returnswitches-1;}intmain(intargc,char*argv[]){cin.tie(0),cout.tie(0),ios::sync_with_stdio(false);intcases0;while(cinBCRQ){if(B0)break;for(inti1;iB;i)cintowers[i].xtowers[i].y;for(inti1;iC;i)cincities[i].xcities[i].y;memset(D,INF,sizeof(D));for(inti1;iC;i)D[i][i]0;for(inti1,m,n;iR;i){cinmn;D[m][n]D[n][m]getSwitchs(m,n);}for(intk1;kC;k)for(inti1;iC;i)for(intj1;jC;j)D[i][j]min(D[i][j],D[i][k]D[k][j]);coutCase cases:\n;for(inti1,s,d;iQ;i){cinsd;if(D[s][d]INF)coutImpossible;elsecoutD[s][d];cout\n;}}return0;}总结本题的关键在于将“沿道路行驶时的基站切换次数”转化为“道路线段穿过的Voronoi\texttt{Voronoi}Voronoi小区边界数量”。通过计算每个BTS\texttt{BTS}BTS塔到线段的最近点并判断该点是否被其他塔更近地覆盖可以确定该塔是否在线段上形成一段势力范围。统计势力范围的数量并减111即得切换次数。随后使用Floyd\texttt{Floyd}Floyd算法求解带权图上的最短路径即可。需要注意浮点数比较的精度问题代码中采用严格小于号进行判断在题目给定的约束下能够正确工作。
区别)
