スポンサーサイト

--.--.-- --:--  スポンサー広告

上記の広告は1ヶ月以上更新のないブログに表示されています。
新しい記事を書く事で広告が消せます。

| - | - | ↑ページトップ |




都市間の距離

2008.09.13 23:01  ACM/ICPC 2008

問題 パソコン甲子園2008 05

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


解説

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

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

pck200805_1.gif


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

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

さらに以下の図で、

pck200805_2.gif


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 }



スポンサーサイト

テーマ : プログラミング - ジャンル : コンピュータ

| コメント(0) | トラックバック(0) | ↑ページトップ |

この記事へのコメント

コメントを書く


管理人にのみ表示

↑ページトップ

この記事へのトラックバック

この記事にトラックバックする(FC2ブログユーザー)

↑ページトップ

上記広告は1ヶ月以上更新のないブログに表示されています。新しい記事を書くことで広告を消せます。