Description

给定两个圆 \(A\) 和 \(B\) 的圆心坐标和半径，以及初始速度。现需改变 \(A\) 的速度，使得在 \(t=0 \sim 1s\) 时，两个圆不会碰撞（相交）。求出 \(\min\{|\Delta v_A|\}\) 。

Solution

不妨将 \(A\) 平移至原点，建立极坐标系。并以 \(B\) 为参考系，算出 \(A\) 的相对速度 \(V=v_A-v_B\)。两圆不相交等价于 \(|AB|\geq r1+r2\)。于是不妨将 \(A\) 的半径加给 \(B\)，而 \(A\) 转换为点。于是问题变为了将 \(V\) 移出红线之外的最短距离，如图。

会发现，最短距离就是到两条切线的距离，或到圆弧的距离，分类讨论一下。主要注意一下写法，转化为极坐标之后，操作非常方便。

另外注意，只有当 \(V\) 位于 \(AEBD\) 内的时候，到圆弧的距离才有效，用三角剖分判断是否在内部。

#include<stdio.h>
#include<math.h>
#include<algorithm>

using namespace std;

#define vec(x,n) Point(x*cos(n),x*sin(n))

typedef double db;

struct Point{
	db x,y;
	Point(db x_=0.0,db y_=0.0):x(x_),y(y_){}
	Point operator -(const Point &X){
		return Point(x-X.x,y-X.y);
	}
	db operator *(const Point &X){
		return x*X.y-y*X.x;
	}
	void read(){scanf("%lf%lf",&x,&y);}
	db len(){return sqrt(x*x+y*y);}
}pa,pb,va,vb;

db r1,r2;

const db tau=acos(-1.0)*2;

inline db Rg(db n){
	db ret=n-(floor(n/tau)-1)*tau;
	return ret>=tau? ret-tau:ret;
}

int main(){
	int T; scanf("%d",&T);
	while(T--){
		scanf("%lf",&r1); pa.read(),va.read();
		scanf("%lf",&r2); pb.read(),vb.read();
		
		db R=r1+r2;
		Point P=pb-pa,V=va-vb;
		db n1=Rg(atan2(P.y,P.x)),n2=Rg(asin(R/P.len()));
		db l1=Rg(n1-n2),l2=Rg(n1+n2);
		
		Point ret1=vec(1,l1);
		if(V*ret1>=0||V*vec(1,l2)<=0){
			printf("0.0000000000\n");
			continue;
		}
		
		db n3=atan(V.y/V.x);
		db ans=min(fabs(sin(Rg(l2-n3))),fabs(sin(Rg(n3-l1))))*V.len();
		
		db d=P.len()*cos(n2);
		Point A(0,0),B=vec(d,l1),C=vec(d,l2);
		Point D[4]={A,B,P,C};
		bool flag=1;
		for(int i=0;i<4;i++)
			flag&=((D[i]-V)*(D[(i+1)%4]-V)>=0);
		if(flag) ans=min(ans,max(R-(V-P).len(),0.0));
		
		printf("%.10lf\n",ans);
	}
}