3129:How I Wonder What You Are!

keyword

空間幾何　C

概要

空間状に星がN(<500)個ある。また原点にライトがM(<50)本ある。各ライトには向き dirと角度 φが設定されていて、星への方向ベクトルとdirのなす角度がφ以下ならその星は照らされる。照らされている星の個数を求める問題。
何の工夫もなく角度を求めるだけ。計算量O(N*M)。あとPKUでGCCを選んだときは-lmがついていることも確認できた。

double sx[501], sy[501], sz[501];
double lx[51], ly[51], lz[51], angs[51];

double getArg(int i, int j){
    return acos((sx[i]*lx[j] + sy[i]*ly[j] + sz[i]*lz[j])
                 /(sqrt(sx[i]*sx[i]+sy[i]*sy[i]+sz[i]*sz[i])*
                   sqrt(lx[j]*lx[j]+ly[j]*ly[j]+lz[j]*lz[j])));
}

int main(){
    int n, m, i, j, ans;
    while(scanf("%d",&n), n){
        for(i=0;i<n;i++) scanf("%lf%lf%lf",sx+i,sy+i,sz+i);
        scanf("%d",&m);
        for(i=0;i<m;i++) scanf("%lf%lf%lf%lf",lx+i,ly+i,lz+i,angs+i);

        ans = 0;
        for(i=0;i<n;i++){
            for(j=0;j<m;j++){
                if( getArg(i,j) < angs[j] ){
                    ans++;
                    break;
                }
            }
        }

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