ぱーぽーの競プロ記

競技プログラミングに関することを書きます。

AOJ 1266 How I Wonder What You Are!

・概要
問題文はこちら
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=1266

3次元空間にたくさんの星があります。望遠鏡を使って何個の星が見えるかを求める問題です。


・解法
この問題は内積の公式を覚えていれば簡単に解くことができます。

A・B = |A||B|cosθより
θ = acos(A・B/|A||B|)


ソースコード

#include<iostream>
#include<set>
#include<cmath>
using namespace std;

static const double EPS = 1e-9;

struct Star{
   double x,y,z;
   Star(){}
   Star(double x, double y, double z):x(x),y(y),z(z){}
   
   double dist(){
      return sqrt(x*x+y*y+z*z);
   }
};

bool canSee(double x, double y, double z, double phi, Star star){
   double theta = acos((x*star.x+y*star.y+z*star.z)/sqrt((x*x+y*y+z*z))/star.dist());
   return theta <= phi + EPS;
}

int main(){
   int n,m;
   Star star[500];
   while(cin >> n){
      if(n==0)break;

      double x,y,z;
      set<int> ans;

      for(int i = 0 ; i < n ; i++){
         cin >> x >> y >> z;
         star[i] = Star(x,y,z);
      }
      
      cin >> m;
      
      for(int i = 0 ; i < m ; i++){
         double phi;
         cin >> x >> y >> z >> phi;
         for(int j = 0 ; j < n ; j++){
            if(canSee(x,y,z,phi,star[j]))ans.insert(j);
         }
      }

      cout << ans.size() << endl;
   }
   return 0;
}