AOJ : 1266 - How I Wonder What You Are!

AOJ ACM-ICPC 幾何

問題概要

http://rose.u-aizu.ac.jp/onlinejudge/ProblemSet/description.jsp?id=1266

複数の星の座標が(x,y,z)で与えられます。
自分が所持している望遠鏡を使用して、それらの星の内、何個見ることができるかどうかを答える問題です。

望遠鏡を複数個もっていて、使用する望遠鏡によって観れる方向と範囲が変化します。
望遠鏡で見える範囲は、入力では

  • x y z phi

の順で与えられます。
(x,y,z)の方向のベクトルとphiの角度をなす円錐の形をした範囲が望遠鏡で見える範囲です。（問題の図を見ればわかります）

アルゴリズム

高校数学を覚えているかどうかの問題です。
星と望遠鏡を一つずつ選び、それらのベクトルの内積をとって、次の公式に当てはめて計算します。
ベクトルのなす角
この公式で得られた解が、望遠鏡のphi以下であれば星を見ることができる、ということになります。

あとは、これを二重ループでまわすだけです。

プログラム

#include <stdio.h>
#include <math.h>

#define EPS 1e-10
#define rep(i,n) for(i=0;i<n;i++)

typedef struct{
	double x,y,z;
}P;

double dot(P a,P b){
	return a.x * b.x + a.y * b.y + a.z * b.z;
}

double dist(P a){
	return sqrt(a.x*a.x + a.y*a.y + a.z*a.z);
}

double getTheta(P a,P b){
	return acos(dot(a,b) / (dist(a) * dist(b)));
}

int main(void){
	int i,j;
	int n,m,ans;
	double phi[50];
	P s[500],t[50];

	while(scanf("%d",&n) && n){
		rep(i,n) scanf("%lf%lf%lf",&s[i].x,&s[i].y,&s[i].z);
		scanf("%d",&m);
		rep(i,m) scanf("%lf%lf%lf%lf",&t[i].x,&t[i].y,&t[i].z,&phi[i]);

		ans = 0;
		rep(i,n)rep(j,m){
			if(getTheta(s[i],t[j]) < phi[j] + EPS){
				ans++;
				break;
			}
		}

		printf("%d\n",ans);
	}

	return 0;
}