HDU 2912

直線關于球的多次反射，求最后一次反射點

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>using namespace std;
const double inf=1e10;
const double eps=1e-8;
struct point {double x,y,z;
//    point (double _x,double _y,double _z){ x=_x; y=_y; z=_z; };
};
struct sphe {point cent;double r;
};
struct vect {point st,des;
};
sphe cir[110];vect livc;
int n;point operator -(const point &u,const 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 dot(point x,point y){return x.x*y.x+x.y*y.y+x.z*y.z;
}point xmulti(point u,point v){point ret;ret.x=(u.y*v.z-v.y*u.z);ret.y=(u.z*v.x-u.x*v.z);ret.z=(u.x*v.y-u.y*v.x);return ret;
}double dis(point x,point y){return sqrt((x.x-y.x)*(x.x-y.x)+(x.y-y.y)*(x.y-y.y)+(x.z-y.z)*(x.z-y.z));
}double vlen(point x){return sqrt(x.x*x.x+x.y*x.y+x.z*x.z);
}point  construct(){point crop;crop.x=crop.y=crop.z=0;double stoc=inf; point tmpcrop; point foot,tmpfoot; bool flag; point tmp; int k;while(true){flag=false; stoc=inf;for(int i=0;i<n;i++){if(dot(livc.des-livc.st,cir[i].cent-livc.st)>=-eps){//判斷圓是否與直線同向，通過點積判方向 double D=vlen(xmulti(livc.des-livc.st,cir[i].cent-livc.st))/dis(livc.st,livc.des);  //    cout<<D<<' '<<i<<endl;if(D-cir[i].r<=eps){       //半徑小于D,相交 flag=true;//    cout<<"YES"<<endl;double u=dot(cir[i].cent-livc.st,livc.des-livc.st)/(dis(livc.st,livc.des)*dis(livc.st,livc.des));//計算垂足。可通過向量的比例所得方程，聯合垂直點積為0的方程解得 tmpfoot=livc.st;tmpfoot.x+=u*(livc.des.x-livc.st.x);tmpfoot.y+=u*(livc.des.y-livc.st.y);tmpfoot.z+=u*(livc.des.z-livc.st.z);//    cout<<tmpfoot.x<<' '<<tmpfoot.y<<' '<<tmpfoot.z<<' '<<endl;u=sqrt((cir[i].r*cir[i].r-D*D))/dis(livc.st,livc.des);  //計算交點。垂足到圓上交點方向與直線反方向相同//通過兩者距離比計算出向量的轉化 tmpcrop=tmpfoot;tmp=livc.st-livc.des;tmpcrop.x+=tmp.x*u;tmpcrop.y+=tmp.y*u;tmpcrop.z+=tmp.z*u;D=dis(tmpcrop,livc.st);//    cout<<D<<endl;if(D<stoc){     //若與多個圓相交，選取較近的一個 stoc=D; crop=tmpcrop;k=i;}}}}if(!flag) return crop;double tu=dot(livc.st-cir[k].cent,crop-cir[k].cent)/(dis(crop,cir[k].cent)*dis(crop,cir[k].cent));tmpfoot=cir[k].cent;     //計算反射線。直線st點關于交點與球心的直線 對稱點作為反射線的des點 tmpfoot.x+=tu*(crop.x-cir[k].cent.x);tmpfoot.y+=tu*(crop.y-cir[k].cent.y);tmpfoot.z+=tu*(crop.z-cir[k].cent.z);    //知直線st點到反射線des點的方向與st點到關于對稱線垂足方向相同且為兩倍 livc.des.x=((tmpfoot.x-livc.st.x)*2+livc.st.x);  //通過這樣可以求對稱點 livc.des.y=((tmpfoot.y-livc.st.y)*2+livc.st.y);livc.des.z=((tmpfoot.z-livc.st.z)*2+livc.st.z);livc.st=crop;//    cout<<livc.des.x<<' '<<livc.des.x<<' '<<livc.des.x<<endl;}
}int main(){point tmp; double r;while(scanf("%d",&n),n){livc.st.x=livc.st.y=livc.st.z=0;scanf("%lf%lf%lf",&tmp.x,&tmp.y,&tmp.z);livc.des=tmp;for(int i=0;i<n;i++){scanf("%lf%lf%lf%lf",&cir[i].cent.x,&cir[i].cent.y,&cir[i].cent.z,&cir[i].r);}tmp=construct();printf("%.4lf %.4lf %.4lf\n",tmp.x,tmp.y,tmp.z);}
}