http://poj.org/problem?id=1263
#include<iostream>
#include"math.h"
using namespace std;
const double pi=3.14159265358979324;
struct point
{double x,y;};
struct cir
{point p;
double r;};
struct ray
{point p;
double dx,dy;};
struct line
{double a,b,c;};
//l: ax+by+c=0
inline double sq(double a)
{return a*a;}
line ray_line(ray s)
{line l;double d;
if(s.dx==0){l.a=1;l.b=0;l.c=-s.p.x;return l;}
d=s.dy/s.dx;
l.a=d;l.b=-1;l.c=s.p.y-d*s.p.x;
return l;
}
inline double jl(point &a,point &b)
{return sqrt((a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y));}
inline double jl(line &l,point &p)
{return fabs(l.a*p.x+l.b*p.y+l.c)/sqrt(l.a*l.a+l.b*l.b);}
double jl(cir &c,ray &s)
{line l=ray_line(s);return jl(l,c.p);}
int in_cir(cir &c,point &p)
{return fabs(c.r*c.r-sq(c.p.x-p.x)-sq(c.p.y-p.y))<0.00001;}
point jiao(ray &s,cir &c)
{point n;
double d=jl(c,s),
l=jl(c.p,s.p),
h=sqrt(sq(l)-sq(d)),
f=sqrt(sq(c.r)-sq(d)),
g=h-f,
m=sqrt(sq(s.dx)+sq(s.dy));
n.x=s.p.x+g/m*s.dx;
n.y=s.p.y+g/m*s.dy;
if(!in_cir(c,n)){n.x=s.p.x-g/m*s.dx;n.y=s.p.y-g/m*s.dy;}
return n;
}
ray ref(ray &s,cir &c,point &n)
{ray fs;point vec;double m;
vec.x=n.x-c.p.x;
vec.y=n.y-c.p.y;
m=sqrt(sq(vec.x)+sq(vec.y));
vec.x/=m;vec.y/=m;
m=vec.x*(s.p.x-n.x)+vec.y*(s.p.y-n.y);
vec.x*=2*m;vec.y*=2*m;
fs.p=n;
fs.dx=vec.x-(s.p.x-n.x);
fs.dy=vec.y-(s.p.y-n.y);
return fs;
}
cir c[30];
ray s;int n;
int main()
{int i,j,c_n=0,key;point nb,nt;int b;
while(1)
{cin>>n;
if(n==0)break;
for(i=0;i<n;i++)
cin>>c[i].p.x>>c[i].p.y>>c[i].r;
cin>>s.p.x>>s.p.y>>s.dx>>s.dy;
cout<<"Scene "<<++c_n<<endl;
for(i=0;i<=10;i++)
{key=0;b=-1;
for(j=0;j<n;j++)
if(jl(c[j],s)<c[j].r&&!in_cir(c[j],s.p))
{
nt=jiao(s,c[j]);
if((nt.x-s.p.x)*s.dx>=0&&(nt.y-s.p.y)*s.dy>=0)
{if(key==0){nb=nt;b=j;}
else if(jl(nt,s.p)<jl(nb,s.p)){nb=nt;b=j;}
}
}
if(b==-1){cout<<"inf"<<endl;break;}
else if(i==10)cout<<"..."<<endl;
else {s=ref(s,c[b],nb);
cout<<b+1<<' ';}
}
cout<<endl;
}
return 0;
}