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