poj 1263 Reflections (计算几何 反射)
题目意思：给出几个圆，再给出一个光源点和方向，模拟反射过程
解题思路：
1.求出射线;
2.求出在这条射线方向与圆的第一个交点，也就判断出是哪个圆;
3.把交点做为光源，求对称点，再反回步骤1。
难点在第二步，即要判断是否有两个交点（题目中已给出没有一个交点的情况）
还要判断这个交点是否是离光源最近的一点(不是刚反射过的那个圆)，
还有要注意的是这是射线，不是直线，求出交点时要判断方向。
//PS: CE了n多次，最后把using namespace std;删掉就好了。太坑了。
#include<iostream>#include<cstdio>#include<math.h>#define eps 1e-8#define INF 10000000000.0#define zeor(x) (x>0.0 ? x<eps:-x<eps )struct Point{double x,y;};struct Line{double a,b,c;};struct Circle{double r;Point center;};struct pOnCircle{int cnt;double dis;double x,y;};Circle c[30];int n;//两点距离double distance(Point p1,Point p2){return sqrt((p1.x-p2.x)*(p1.x-p2.x)+(p1.y-p2.y)*(p1.y-p2.y));}//求点到线距离double pToline(Point p,Line l){return fabs(l.a*p.x+l.b*p.y+l.c)/sqrt(l.a*l.a+l.b*l.b);}//两点求线Line twoPoLine(Point p1,Point p2){Line l;l.a=p2.y-p1.y;l.b=p1.x-p2.x;l.c=p2.x*p1.y-p1.x*p2.y;return l;}//求点关于线对称点Point pLinePoint(Point p,Line l){Point p2;double d=l.a*l.a+l.b*l.b;p2.x=((l.b*l.b-l.a*l.a)*p.x-2*l.a*l.b*p.y-2*l.a*l.c)/d;p2.y=((l.a*l.a-l.b*l.b)*p.y-2*l.a*l.b*p.x-2*l.b*l.c)/d;return p2;}//求两条直线的交点(保证相交)Point intersection(Point p1,Point p2,Point p3,Point p4){Point ret=p1;// double t=xmult_4(p3,p1,p3,p4)/xmult_4(p1,p2,p3,p4);double t=((p1.x-p3.x)*(p3.y-p4.y)-(p1.y-p3.y)*(p3.x-p4.x))/((p1.x-p2.x)*(p3.y-p4.y)-(p3.x-p4.x)*(p1.y-p2.y));ret.x+=(p2.x-p1.x)*t;ret.y+=(p2.y-p1.y)*t;return ret;}//求直线与圆的交点（保证有交点）void interLineCircle(double r,Point center,Point l1,Point l2,Point &p1,Point &p2){Point p=center;p.x+=l1.y-l2.y;p.y+=l2.x-l1.x;p=intersection(p,center,l1,l2);double temp=distance(l1,l2);double dis=distance(center,p);double t=sqrt(r*r-dis*dis)/temp;p1.x=p.x+(l2.x-l1.x)*t;p1.y=p.y+(l2.y-l1.y)*t;p2.x=p.x+(l1.x-l2.x)*t;p2.y=p.y+(l1.y-l2.y)*t;}//判断方向是否正确bool isDir(Point orign,Point dir,Point inter)//ps: 在这里纠结好久{return (dir.x*(inter.x-orign.x)+(inter.y-orign.y)*dir.y)>=0;}void fun(Point ori,Point d){int num=0;pOnCircle node;Point dir=d;Point orign=ori;while(true){node.dis=INF;int i,j,cnt=0;Point temp;temp.x=orign.x+dir.x;temp.y=orign.y+dir.y;Line l=twoPoLine(orign,temp);for(i=1;i<=n;i++)if(i!=node.cnt&&c[i].r-pToline(c[i].center,l)>eps){//求第一个交点Point p[2];double dis[2];interLineCircle(c[i].r,c[i].center,orign,temp,p[0],p[1]);//求直线与圆的交点dis[0]=distance(p[0],orign);dis[1]=distance(p[1],orign);int index=(dis[0]-dis[1]>=eps ?1:0);if(isDir(orign,dir,p[index]))//方向判断{// printf("ori: %lf %lf\n",orign.x,orign.y);if(dis[index]>eps && node.dis- dis[index] >=eps){node.dis=dis[index];node.x=p[index].x;node.y=p[index].y;node.cnt=i;}}}if(INF-node.dis>eps){// printf("node.dis: %lf\n",node.dis);if(num>=10){printf("...\n");return ;}else{printf("%d ",node.cnt);num++;Point inter;inter.x=node.x;inter.y=node.y;// printf("inter : %lf %lf\n",inter.x,inter.y);Line lin=twoPoLine(c[node.cnt].center,inter);Point next=pLinePoint(orign,lin);dir.x=next.x-inter.x;dir.y=next.y-inter.y;orign.x=inter.x;orign.y=inter.y;// printf("next : %lf %lf\n",next.x,next.y);// printf("dir : %lf %lf\n",dir.x,dir.y);}}else{printf("inf\n");return ;}}}int main(){int i,j,k=1;// freopen("fzu1035.txt","r",stdin);while(scanf("%d",&n),n){for(i=1;i<=n;i++){scanf("%lf %lf %lf",&c[i].center.x,&c[i].center.y,&c[i].r);}Point orign;Point dir;scanf("%lf %lf %lf %lf",&orign.x,&orign.y,&dir.x,&dir.y);printf("Scene %d\n",k++);fun(orign,dir);printf("\n");}return 0;}