题目描述题目要求计算地球表面上两个城市之间的球面距离大圆距离。地球被视为半径为637863786378km\texttt{km}km的完美球体。输入包含城市列表和查询列表每个查询输出两个城市之间的距离四舍五入到整数若城市不存在则输出Unknown。输入格式城市列表每行一个城市名、纬度−90∘-90^\circ−90∘到90∘90^\circ90∘、经度−180∘-180^\circ−180∘到180∘180^\circ180∘以#结束。查询列表每行两个城市名以# #结束。输出格式对于每个查询输出一行A - B然后输出一行距离保留整数或Unknown。样例输入Ulm 48.700 10.500 Freiburg 47.700 9.500 Philadelphia 39.883 -75.250 SanJose 37.366 -121.933 NorthPole 90 0 SouthPole -90 0 # Ulm Philadelphia Ulm SanJose Freiburg Philadelphia Freiburg SanJose Ulm Freiburg SanJose Philadelphia Ulm LasVegas Ulm Ulm Ulm NorthPole Ulm SouthPole NorthPole SouthPole # #输出Ulm - Philadelphia 6536 km Ulm - SanJose 9367 km Freiburg - Philadelphia 6519 km Freiburg - SanJose 9412 km Ulm - Freiburg 134 km SanJose - Philadelphia 4023 km Ulm - LasVegas Unknown Ulm - Ulm 0 km Ulm - NorthPole 4597 km Ulm - SouthPole 15440 km NorthPole - SouthPole 20037 km题目分析本题的核心是计算球面上两点之间的大圆距离。球面距离公式给定两点的经纬度(ϕ1,λ1)(\phi_1, \lambda_1)(ϕ1,λ1)和(ϕ2,λ2)(\phi_2, \lambda_2)(ϕ2,λ2)弧度制大圆距离为dR⋅arccos(sinϕ1sinϕ2cosϕ1cosϕ2cos(λ1−λ2)) d R \cdot \arccos(\sin \phi_1 \sin \phi_2 \cos \phi_1 \cos \phi_2 \cos(\lambda_1 - \lambda_2))dR⋅arccos(sinϕ1sinϕ2cosϕ1cosϕ2cos(λ1−λ2))其中R6378R 6378R6378km\texttt{km}km。该公式在数值不稳定时如两点接近可使用半正矢公式haversine\texttt{haversine}haversine替代。算法步骤读取城市列表存储名称到经纬度转换为弧度的映射。对于每个查询查找两个城市是否存在若任一不存在输出Unknown。否则计算大圆距离四舍五入到整数输出。复杂度分析城市数≤100\le 100≤100查询数未知每次查询O(1)O(1)O(1)。代码实现// Globetrotter// UVa ID: 535// Verdict: Accepted// Submission Date: 2016-08-18// UVa Run Time: 0.000s//// 版权所有C2016邱秋。metaphysis # yeah dot net#includebits/stdc.husingnamespacestd;constdoublePI2*acos(0),R6378.0;doublegcd(doubleR,doubleplat,doubleplong,doubleqlat,doubleqlong){returnR*acos(sin(plat)*sin(qlat)cos(plat)*cos(qlat)*cos(plong-qlong));}doublehaversine(doubleR,doubleplat,doubleplong,doubleqlat,doubleqlong){doubledlonqlong-plong;doubledlatqlat-plat;doubleapow((sin(dlat/2)),2)cos(plat)*cos(qlat)*pow(sin(dlon/2),2);doublec2*atan2(sqrt(a),sqrt(1-a));doubledR*c;returnd;}intmain(){cin.tie(0);cout.tie(0);ios::sync_with_stdio(false);string city,from,to;mapstring,pairdouble,doublelocation;doublelatitude,longtitude;while(cincity,city!#){cinlatitudelongtitude;location[city]make_pair(latitude*PI/180.0,longtitude*PI/180.0);}while(cinfromto,from!#){coutfrom - to\n;if(location.find(from)location.end()||location.find(to)location.end())coutUnknown\n;else{doubleDhaversine(R,location[from].first,location[from].second,location[to].first,location[to].second);coutfixedsetprecision(0)D km\n;}}return0;}
