|
|
Posted on 2010-09-07 23:45 Uriel 閱讀(329) 評論(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;
}
|