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));
}