AOJ0177 Distance Between Two Cities

AOJ Volume1

問題リンク Distance Between Two Cities

  • 解法

バリバリ数学問題です。
まず、2つの都市間の最短距離は、円の中心と2つの都市を通るようにスパッと球を切断したときの円弧の長さとなります。
切断面の半径Rは球の半径と同じなので、2つの都市それぞれの座標(x,y,z)を知ることができたら、それらのベクトルのなす角αを使って、
dist = 2*π*R*(α/(2*π)) = R*α
と求めることができます。
北緯 n(ラジアン)、東経 e(ラジアン）から都市の座標を求める方法を説明します。xを右方向、yを奥方向、zを北極点方向を正とする座標軸と考えます。
まず、nを使えば都市の存在するZ座標が求まります。
Z = R*sin(n)
です。
次に球の方程式
x^2 + y^2 + z^2 = R^2
に求まったZを代入して、
x^2 + y^2 = R^2 - (R*sin(n))^2
を得ます。これは、zをR*sin(n)に固定した時の球における切断面となります。この円周上の適当な1点をとります。
x = 0として、円の方程式から
y = -R*√(1-sin(n)^2)
と適当に取ります。
今円周上の点(0, y)にいます。これを角度 e だけ回転させると都市のX座標、Y座標が求まります。
回転式より、
X = sin(e) * y
Y = -cos(e) * y
を得ます。これで北緯n、東経eの都市の座標が(X, Y, Z)だと求まりました。もう1つの都市についても同様に求めます。
求まった2つのベクトルa、bのなす角αは、内積の公式より、
α = acos(a・b / (|a|*|b|))
と求まります。

  • ソース
import java.util.Scanner;
import static java.lang.Math.*;

//Distance Between Two Cities
public class AOJ0177 {

	double R = 6378.1;
	
	double[] get(double n, double e){
		n = n*PI/180; e = e*PI/180;
		return new double[]{R*Math.sqrt((1-sin(n)*sin(n)))*sin(e), -R*Math.sqrt((1-sin(n)*sin(n)))*cos(e), R*sin(n)};
	}

	void run(){
		Scanner sc = new Scanner(System.in);
		for(;;){
			double n1 = sc.nextDouble(), e1 = sc.nextDouble(), n2 = sc.nextDouble(), e2 = sc.nextDouble();
			if(n1==-1&&e1==-1&&n2==-1&&e2==-1)break;
			double[] a = get(n1, e1), b = get(n2, e2);
			double x = acos((a[0]*b[0]+a[1]*b[1]+a[2]*b[2])/(Math.sqrt(a[0]*a[0]+a[1]*a[1]+a[2]*a[2])*Math.sqrt(b[0]*b[0]+b[1]*b[1]+b[2]*b[2])));
			System.out.printf("%.0f\n", R*x);
		}
	}
	
	public static void main(String[] args) {
		new AOJ0177().run();
	}
}