|
|
Posted on 2010-09-07 23:45 Uriel 阅读(297) 评论(0) 编辑 收藏 引用 所属分类: POJ 、 计算几何
找了一晚上计算几何题，看一道一道不会的。。终于找到一道大水。。。 题意是有天空有N颗星星，给出它们的三维坐标。。在(0,0,0)处放着M个望远镜，给出它们的仰角(tx,ty,tz)以及望远镜圆锥形的顶角phi，求总共能看见多少星星。。 方法就是暴力N*M，一个个的判，貌似是第一还是第二次用浙大模板的三维几何~~
 //Problem: 3129 User: Uriel
//Memory: 228K Time: 47MS
//Language: C++ Result: Accepted
#include<math.h>
#include<stdio.h>
#include<stdlib.h>
  struct point {
 bool flag;
double x,y,z;
 }p[550];
struct tele{
double x,y,z,tx,ty,tz,phi;
}tel[55];
int n,m;
double vlen(point p){
return sqrt(p.x*p.x+p.y*p.y+p.z*p.z);
}
double dmult(point u,point v){
return u.x*v.x+u.y*v.y+u.z*v.z;
}
point subt(point u,point v){
point ret;
ret.x=u.x-v.x;
ret.y=u.y-v.y;
ret.z=u.z-v.z;
return ret;
}
double angle_cos(point u1,point u2,point v1,point v2){
return dmult(subt(u1,u2),subt(v1,v2))/vlen(subt(u1,u2))/vlen(subt(v1,v2));
}
int main(){
int i,j,cnt;
  while(scanf("%d",&n),n){
for(i=0;i<n;i++){
p[i].flag=false;
scanf("%lf %lf %lf",&p[i].x,&p[i].y,&p[i].z);
 }
scanf("%d",&m);
for(i=0;i<m;i++){
scanf("%lf %lf %lf %lf",&tel[i].tx,&tel[i].ty,&tel[i].tz,&tel[i].phi);
tel[i].x=0.0;
tel[i].y=0.0;
tel[i].y=0.0;
}
cnt=0;
for(i=0;i<m;i++){
point tmp,ori;
ori.x=0.0;
ori.y=0.0;
ori.z=0.0;
tmp.x=tel[i].tx;
tmp.y=tel[i].ty;
tmp.z=tel[i].tz;
for(j=0;j<n;j++){
if(p[j].flag)continue;
if(acos(angle_cos(ori,tmp,ori,p[j]))<tel[i].phi){
cnt++;
p[j].flag=true;
}
}
}
printf("%d\n",cnt);
}
return 0;
}
|