|
Posted on 2010-09-07 23:45 Uriel 阅读(296) 评论(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; }
|