Poj Solution 1263

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