PKU : 3407 - Brookebond s'en va en guerre...
問題概要
http://poj.org/problem?id=3407
球のA地点とB地点が, 緯度と経度で与えられます.
このとき, AからBまでの球上での最短距離を求めてください.
アルゴリズム
座標とか角度とか求めてがんばりましょう.
プログラム
class P{ public: double x,y,z; P(){} P(double _x,double _y,double _z){ x = _x; y = _y; z = _z; } P operator-(const P &a)const{ return P(x - a.x, y - a.y, z - a.z); } }; double r; //ベクトルpのノルムを求める double absolute(P p){ return sqrt(p.x * p.x + p.y * p.y + p.z * p.z); } P getP(){ double a,b,c,d,x,y,z,tmp; string NS,EW; cin>>a>>b>>NS>>c>>d>>EW; double radNS = (NS == "N" ? 1 : -1) * (a + b / 60) * PI / 180; double radEW = (EW == "E" ? 1 : -1) * (c + d / 60) * PI / 180; z = r * sin(radNS); tmp = r * cos(radNS); x = tmp * sin(radEW); y = tmp * cos(radEW); return P(x,y,z); } double getAns(P a,P b){ double AB = absolute(b-a); //aとbのユークリッド距離 double rad = acos((2 * r * r - AB * AB) / (2 * r * r)); //余弦定理で間の角度を求める return 2 * PI * r * rad / 2 / PI; //球の弧の長さを求める } int main(){ r = 6370; //地球の半径 P a = getP(); P b = getP(); printf("%.3f\n",getAns(a,b)); }