POJ 3129 - How I Wonder What You Are!

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

概要

3次元上の n 個の星の座標 (sx, sy, sz) が与えられる． m 個の望遠鏡が原点にあり，その望遠鏡からは原点に関して (tx, ty, tz) となす角が φ 以下にある星を見ることができる．

n 個のうち何個の星を見ることができるかを答える．

制約

• テストケース < 50
• 0 < n <= 500
• 0 < m <= 50
• -1000 <= sx, sy, sz <= 1000, (sx, sy, sz) != (0, 0, 0)
• -1000 <= tx, ty, tz <= 1000, (tx, ty, tz) != (0, 0, 0)
• 0 <= φ <= π/2
• | ある星とある望遠鏡の (tx, ty, tz) のなす角 | > 10^-8

解法

やるだけ．

 1 #include <cstdio>
 2 #include <vector>
 3 #include <algorithm>
 4 #include <cmath>
 5 using namespace std;
 6 static const double EPS = 1e-6;
 7 
 8 struct P
 9 {
10   double x, y, z;
11 
12   inline double dot(const P& a) const
13   {
14     return x*a.x + y*a.y + z*a.z;
15   }
16 
17   inline double norm() const
18   {
19     return sqrt(dot(*this));
20   }
21 
22   inline double angle(const P& a) const
23   {
24     return acos(dot(a) / (norm() * a.norm()));
25   }
26 };
27 
28 struct observable
29 {
30   typedef vector<pair<P,double> >::const_iterator iter;
31   iter first, last;
32   observable(const iter& f, const iter& l) : first(f), last(l) {}
33   bool operator()(const P& p) const
34   {
35     for (iter it = first; it != last; ++it) {
36       if (p.angle(it->first) < it->second + EPS) {
37         return true;
38       }
39     }
40     return false;
41   }
42 };
43 
44 int main()
45 {
46   int N;
47   while (scanf("%d", &N) != EOF && N != 0) {
48     vector<P> ps(N);
49     for (int i = 0; i < N; i++) {
50       scanf("%lf %lf %lf", &ps[i].x, &ps[i].y, &ps[i].z);
51     }
52     int M;
53     scanf("%d", &M);
54     vector<pair<P,double> > qs(M);
55     for (int i = 0; i < M; i++) {
56       scanf("%lf %lf %lf %lf", &qs[i].first.x, &qs[i].first.y, &qs[i].first.z, &qs[i].second);
57     }
58     printf("%ld\n", count_if(ps.begin(), ps.end(), observable(qs.begin(), qs.end())));
59   }
60   return 0;
61 }