1263.txt

来自「北大ACM题目例程 详细的解答过程 程序实现 算法分析」· 文本 代码 · 共 112 行

#include"iostream.h"
#include"math.h"
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;
}