POJ 2571 - Global Roaming

http://poj.org/problem?id=2571

概要

地球上のある地点の上空 \(h\) km の位置に人工衛星があり、そこから地平線まで電波を飛ばすことができる。 与えられた \(n\) 個の地点の位置が与えられるので、それらのうち人工衛星からの電波を受け取ることができるものだけを答える。

位置は緯度と経度によって与えられる。 地球は半径6387kmの完全な球だとし、人工衛星は点とみなす。

制約

特になし

解法

各地点と人工衛星の位置とがなす各の大きさを求め、それが人工衛星から地平線までの角度より小さいものだけを出力する。 前者は緯度と経度で与えられた位置を三次元座標に変換して内積を計算することで得られ、後者は水平線の位置・地球の中心・人工衛星の位置が直角三角形をなすことから得られる。

どちらもまずコサインの値が得られるので、以下のコードではその値で大小比較している。

 1 #include <cstdio>
 2 #include <cmath>
 3 using namespace std;
 4 static const double PI = acos(-1.0);
 5 static const double EPS = 1e-6;
 6 
 7 struct P3
 8 {
 9   double x, y, z;
10   P3() {}
11   P3(double a, double b, double c) : x(a), y(b), z(c) {}
12 };
13 inline double dot(const P3& p, const P3& q) { return p.x*q.x + p.y*q.y + p.z*q.z; }
14 inline double abs(const P3& p) { return sqrt(dot(p, p)); }
15 
16 static const double R = 6378;
17 
18 P3 from_polar(double lat, double lan, double r)
19 {
20   lat = lat/180.0*PI;
21   lan = lan/180.0*PI;
22   double x = r*cos(lat)*cos(lan);
23   double y = r*cos(lat)*sin(lan);
24   double z = r*sin(lat);
25   return P3(x, y, z);
26 }
27 
28 int main()
29 {
30   int N;
31   for (int Ti = 1; scanf("%d", &N) != EOF && N != 0; Ti++) {
32     double lat, lan, height;
33     scanf("%lf %lf %lf", &lat, &lan, &height);
34     const P3 sat = from_polar(lat, lan, R + height);
35     const double u = R / (R + height);
36     printf("Test case %d:\n", Ti);
37     for (int i = 0; i < N; i++) {
38       char name[128];
39       scanf("%s %lf %lf", name, &lat, &lan);
40       const P3 p = from_polar(lat, lan, R);
41       const double t = dot(sat, p)/(abs(sat) * abs(p));
42       if (u - t < EPS) {
43         puts(name);
44       }
45     }
46     putchar('\n');
47   }
48   return 0;
49 }