都市間の距離

問題 パソコン甲子園2008 05

地球上の２つの都市の北緯と東経を入力し、地表距離を計算して出力して下さい。

解説

これは数学の問題です。
入力された２つの角度から球面座標へ変換し、各都市の(x, y, z)座標を求めます。

以下の図で、z 軸から方向ベクトルへの角度を theta、x 軸から半時計回りのxy平面上の角度をphiとすると、



x = r*sin(theta)*cos(phi);
y = r*sin(theta)*sin(phi);
z = r*cos(theta);

となります。２つの都市の座標より、距離 d を求めます。

さらに以下の図で、



s = r*th となります。

th = acos(1 - d*d/(2*r*r))

より、地表距離 s は

s = r*acos(1 - d*d/(2*r*r))

となります。

サンプルプログラム
※ d*d を dist としています(sqrtの計算を避けるため）

001 #include<stdio.h>
002 #include<iostream>
003 #include<cmath>
004 using namespace std;
005 static const double r = 6378.1;
006 static const double PI = acos(-1);
007 
008 class Point{
009     public:
010     double x, y, z;
011     Point(){}
012     Point ( double theta, double phi ){
013         theta = 90 - theta;
014         theta *= (PI/180); // to degree
015         phi *= (PI/180);
016         x = r*sin(theta)*cos(phi);
017         y = r*sin(theta)*sin(phi);
018         z = r*cos(theta);
019     }
020 };
021 
022 double getDistance( Point p1, Point p2 ){
023     return  (p1.x-p2.x)*(p1.x-p2.x)+(p1.y-p2.y)*(p1.y-p2.y)+(p1.z-p2.z)*(p1.z-p2.z);
024 }
025 
026 int main(){
027     double lat1, lat2, lon1, lon2;
028     Point p1, p2;
029     double theta, phi;
030     while( cin >> lat1 >> lon1 >> lat2 >> lon2 ){
031         if ( lat1 == 0 && lon1 == 0 && lat2 == 0 && lon2 == 0 ) break;
032         
033         p1 =  Point( lat1, lon1 );
034         p2 =  Point( lat2, lon2 );
035         
036         double dist = getDistance( p1, p2 );
037         
038         printf("%.0lf\n", r*acos( 1 - dist/(2*r*r)));
039     }
040     
041     return 0;
042 }