AOJ1266 How I Wonder What You Are!

AOJ Volume12

問題リンク How I Wonder What You Are!

  • 概要

N個の星の3次元座標とM個の望遠鏡の置かれている座標と視野角φが与えられる。これらの望遠鏡を使って見ることができる星はいくつあるか答えよ。星 i が望遠鏡 j を使って見えるとは、それらの位置ベクトルの成す角θ(i,j)がθ(i,j)<φ(j)を満たすことをいう。また、1つの星が複数の望遠鏡で覗くことができる場合重複して数えてはならない。
N <= 500
M <= 50

θ(i,j)-φ(j) < 10^-8
  • 解法

2つのベクトルの成す角θ(i,j)を調べていくだけです。2つのベクトルの成す角は内積の式より、
θ = acos(I・J/(|I||J|)
で求まります。

  • ソース
import java.util.Scanner;

//How I Wonder What You Are!
public class AOJ1266 {

	double dot(double[] a, double[] b){
		return a[0]*b[0]+a[1]*b[1]+a[2]*b[2];
	}
	double norm(double[] a){
		return Math.sqrt(a[0]*a[0]+a[1]*a[1]+a[2]*a[2]);
	}
	
	void run(){
		Scanner sc = new Scanner(System.in);
		for(;;){
			int n = sc.nextInt();
			if(n==0)break;
			double[][] p = new double[n][3];
			for(int i=0;i<n;i++)for(int j=0;j<3;j++)p[i][j]=sc.nextDouble();
			int m = sc.nextInt();
			boolean[] u = new boolean[n];
			while(m--!=0){
				double[] t = new double[3];
				for(int i=0;i<3;i++)t[i]=sc.nextDouble();
				double phi = sc.nextDouble();
				for(int i=0;i<n;i++){
					if(u[i])continue;
					double w = Math.acos(dot(p[i], t)/norm(p[i])/norm(t));
					if(w<phi+1e-8)u[i]=true;
				}
			}
			int res = 0;
			for(boolean f:u)if(f)res++;
			System.out.println(res);
		}
	}
	
	public static void main(String[] args) {
		new AOJ1266().run();
	}
}