2210 - Star Watching

AOJ

http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2210

問題

略

解法

回転する角度は日にちと時間から簡単に計算できる。
元の座標から回転軸まわりに回転させたもののｚ座標が０より大きかったらその星はその時間見ることができる。


座標は角度からsin,cosを使って求めることが出来る。
回転について考えたが頭がこんがらがってギブアップ。
解法を調べると、回転行列を使えば良いとのこと。
Wikipediaに各座標軸まわりの回転行列が載っている。
任意の回転軸まわりの回転は、回転軸をある座標軸に重ねた後その座標軸まわりの回転をして元に戻すという操作をすれば良い。


角度の正負なんかに苦労しながらAC。


次の日気になったのでもう少し調べていると、
３次元の回転 (原点を通る任意方向回転軸，座標系に依存しないベクトル表現と回転行列)に、任意の回転軸まわりの回転後のベクトルを求める公式を発見。
ということでそれを用いて書きなおしたのが以下のソースコード。
なお、三次元の座標を表すのにSpaghettiSourceにならってvalarrayを用いた。
valarrayについてはネットに日本語の資料があまり見当たらなかったので、<valarray> - C++ Referenceを見るのがよさそう。

ソース

double rad(double d) {
  return d*PI/180;
}

typedef double number;
typedef valarray<number> point;

// 経度と緯度から座標を計算。球の中心が原点。
// lon : ０度から東まわり　０〜2PI
// lat : 北極から南極方向　０〜PI
// lon=0,lat=PI/2 がｘ軸、lon=PI/2,lat=PI/2 がｙ軸　北極がｚ軸
point coord(double R, double lon, double lat) {
  point res(3);
  res[0] = R*cos(lon)*sin(lat);
  res[1] = R*sin(lon)*sin(lat);
  res[2] = R*cos(lat);
  return res;
}
number dot(const point& a, const point& b) {
  return (a * b).sum();
}
point cross(const point& a, const point& b) {
  return a.cshift(+1)*b.cshift(-1)
       - a.cshift(-1)*b.cshift(+1);
}
// ベクトルまわりの回転 axisは単位ベクトル
point rotate(point axis, double ang, point a) {
  return a * cos(ang) + (1.0 - cos(ang)) * dot(a, axis) * axis + cross(axis, a) * sin(ang);
}

bool judge(double a, double h, double ang) {
  return (rotate(coord(1, 0, rad(46.8)), -ang, coord(10,-a,h))[2] >= 0);
}

int main() {
  int month[12] = {31,29,31,30,31,30,31,31,30,31,30,31};
  int T;
  cin >> T;
  while(T--) {
    int mon,day,hh,mm;
    scanf("%d/%d %d:%d",&mon,&day,&hh,&mm);
    int min = 0;
    REP(i, mon-1)
      min += month[i] * 24 * 60;
    min += (day-1) * 24 * 60 + hh * 60 + mm;
    double ang = rad((1.0+1.0/365.24) * 360 * min / (24 * 60));
    int n;
    cin >> n;
    REP(i,n) {
      string name;
      cin >> name;
      int m;
      cin >> m;
      bool f = 1;
      REP(j,m) {
        double a,h;
        cin >> a >> h;
        h = 90.0 - h;
        if (f && !judge(rad(a), rad(h), ang)) {
          f = 0;
        }
      }
      if (f)
        cout << name <<endl;
    }
  }
}