Uriel's Corner

Research Associate @ Harvard University / Research Interests: Computer Vision, Biomedical Image Analysis, Machine Learning
posts - 0, comments - 50, trackbacks - 0, articles - 594

POJ 3129 How I Wonder What You Are!----计算几何

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;
}


只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理