http://acm.zju.edu.cn/onlinejudge/showProblem.do?problemId=5074
题意:两个圆,小圆为实体,具有碰撞性。其中一个内含于另外一个,另有一枚硬币在大圆外,呈射线发射,求该硬币在大圆内的时间。 分析: 原先思路:圆心和直线的距离dist和R进行比较,R<dist则硬币和圆不相交。 若射线往圆的反方向射,则不会相交,但是用这种方法会判断出相交。 第二个错误的思想在于,虽然将直线转换为射线,没有求出交点,来求出时间t,但却没有判断t>0,若t<0的话,说明射线往反方向走 正确思路,若与大圆么没有两个交点,则时间为0,否则判断和小圆的交点,若没有两个交点,则距离为大圆两个交点距离,否则由于小圆反射 就是大圆和小圆的距离差
交点的数学原理: 圆:圆心为o,其半径为r,则||p-o||=r 射线:起点为p0,其速度方向为u,则p=p0+ut 若射线与圆有交点,则存在某个点pt,(p0+ut-o)^2=r^2 u^2t+2u(p0-o)t+(p0-o)^2-r^2=0; 这样就转换为判断delta来确定交点数量 求出来的t=(-b+-sqrt(b^2-4ac))就为时间 其交点就是p1=p0+ut
#include<stdio.h>
#include<string.h>
#include<math.h>
#define eps 1e-9
struct point
{
double x,y;
};
struct line
{
point a,b;
};
struct circle
{
point p;
double r;
};
double distance(point p0,point p1)
{
return sqrt((p0.x-p1.x)*(p0.x-p1.x)+(p0.y-p1.y)*(p0.y-p1.y));
}
double xmult(point p1,point p2,point p0)
{
return (p1.x-p0.x)*(p2.y-p0.y)-(p2.x-p0.x)*(p1.y-p0.y);
}
double disptoline(circle p,line l)
{
// printf("%lf",xmult(p.p,l.a,l.b));
//printf("%lf",distance(l.a,l.b));
return fabs(xmult(p.p,l.a,l.b))/distance(l.a,l.b);
}
int GetLineInsertion(line l,circle cir,point v,double &t1,double &t2)
{
double a=v.x,c=v.y;
double b=l.a.x-cir.p.x,d=l.a.y-cir.p.y;//p0-o
double f=2*(b*a+d*c);//2*t*u*(po-o)
double e=a*a+c*c;//射线方向的平方
double g=b*b+d*d-cir.r*cir.r;//(po-o)^2-r^2
double delta=f*f-4*e*g;
if(delta<0) return 0;
if(delta==0)
{
t1=t2=-f/(2*e);
}
t1=(-f-sqrt(delta))/(2*e);
t2=(-f+sqrt(delta))/(2*e);
if(t1<0 || t2<0) return 0;//当时间为负数的时候,射线反方向执行
//虽然这样可以符合delta>0
return 2;
}
int main()
{
double R,RM,r;
double k1,k2,k3,k4;
point p1,v,p2;
circle cir_R,cir_RM;
cir_R.p.x=cir_R.p.y=cir_RM.p.x=cir_RM.p.y=0.0;
line l;
point t1,t2,t3,t4;
while(scanf("%lf%lf%lf%lf%lf%lf%lf",&RM,&R,&r,&p1.x,&p1.y,&v.x,&v.y)!=EOF)
{
cir_R.r=R+r;
cir_RM.r=RM+r;
p2.x=p1.x+v.x*10000;
p2.y=p1.y+v.y*10000;
l.a.x=p1.x,l.a.y=p1.y;
l.b.x=p2.x,l.b.y=p2.y;
double dist=disptoline(cir_R,l);//圆心到直线的距离
int flag=GetLineInsertion(l,cir_R,v,k1,k2);
if(flag==0)
{
printf("0.000\n");
}
else
{
t1.x=p1.x+v.x*k1;
t1.y=p1.y+v.y*k1;
t2.x=p1.x+v.x*k2;
t2.y=p1.y+v.y*k2;
flag=GetLineInsertion(l,cir_RM,v,k3,k4);
if(flag==0)//没有和小圆相交
{
double dist_time;
dist_time=distance(t1,t2);
dist_time/=sqrt(v.x*v.x+v.y*v.y);
printf("%.3lf\n",dist_time);
}
else
{
t3.x=p1.x+v.x*k3;
t3.y=p1.y+v.y*k3;
t4.x=p1.x+v.x*k4;
t4.y=p1.y+v.y*k4;
double dist_time;
dist_time=distance(t1,t2)-distance(t3,t4);
dist_time/=sqrt(v.x*v.x+v.y*v.y);
printf("%.3lf\n",dist_time);
}
}
}
return 0;
}