题解：UVA10674 Tangents

zhangyaiwei · 2025-07-10 14:43:41 · 题解

题意

给出两个圆，求这两个圆的公切线（最多有4条）。

题解

圆的公切线可以分为两种：内公切线和外公切线，我们分开处理这两种公切线

内公切线

由于是内公切线，所以我们很容易可以得到 \alpha_1 + \alpha_2 = \pi，我们不妨认设 \alpha_1=\alpha,\alpha_2=\pi-\alpha

所以可以得到 \vec{t}_1=r_1\begin{bmatrix}\cos\alpha\\\sin\alpha\end{bmatrix},\vec{t}_2=-r_2+\begin{bmatrix}\cos\alpha\\\sin\alpha\end{bmatrix}

又因为 \vec{T_1}=\vec{O_1}+\vec{t}_1,\vec{T_2}=\vec{O_2}+\vec{t}_2

所以可以得到 \vec{T_1}=\begin{bmatrix}x_1+r_1\cos\alpha\\y_1+r_1\sin\alpha\end{bmatrix},\vec{T_2}=\begin{bmatrix}x_2-r_2\cos\alpha\\y_2-r_2\sin\alpha\end{bmatrix}

我们现在只要判断 v_1 和 v_2 是否在一条直线上即可，很显然，v_1 和 v_2 的朝向是一致（或相反的），都是 \lambda\begin{bmatrix}-\sin\alpha\\cos\alpha\end{bmatrix}。

有矢量 A+k\vec{v}。如果想让 x_A 变大 t 得到到 A' 后，x_vy_A'-y_vx_A'=x_vy_A-y_vx_A，y_A 也要变大 t\frac{y_v}{x_v}，所以 A'(x_A+t,y_A+t\frac{y_v}{x_v})，此时 A 与 A' 在同一直线上。

而这个过程是可逆的，于是我们得到了如果矢量 A+k\vec{v} 与 B+k\vec{v} 共线的充要条件即是 x_vy_A-y_vx_A=x_vy_B-y_vx_B。

所以，回到上面，如果 v_1 和 v_2 共线，则有 -\sin\alpha y_{T_1}-\cos\alpha x_{T_1}=-\sin\alpha y_{T_2}-\cos\alpha x_{T_2}，令 M_1=-\sin\alpha y_{T_1}-\cos\alpha x_{T_1}，M_2=-\sin\alpha y_{T_2}-\cos\alpha x_{T_2}

如果 M_1=M_2，即

外公切线

大部分内容其实和内公切线基本一致，主要的区别就是 \alpha_1=\alpha_2=\alpha，所以 M_2 变成了和 M_1 一样的形式，即 M_2=-y_2sin\alpha-x_2\cos\alpha-r_2。

同样的用 M_1 和 M_2 做差，得到条件为

求解方程

现在我们已经求出了两个方程，我们只需要分别求解就可以得到答案，但怎么解呢？这里提供一种神奇的方法。

对于方程 a\cos\alpha+b\sin\alpha+c=0，可以看成一个方程组：

注意到这个方程组表示的正是圆和直线的交点

但是斜的线和圆求交点不是很好求，但是若是平行于 x 轴的的话就好求一些了。对于直线 y=h，和单位圆的交点 y 坐标就是 h。而 x 坐标的话，可以用反三角函数（\arcsin）求出圆心角，再对称地复制一份即可。

但是我们可以通过旋转来将斜的线强行变成水平的，之后再转回来即可。转成的直线解析式即为 y=d，这里的 d 为原直线到圆心（原点）的距离。根据直线一般式到点的距离公式，可以轻易得到 d=\frac{|ax_O+by_O+c|}{\sqrt{a^2+b^2}}=\frac{|c|}{\sqrt{a^2+b^2}}。

所以我们可以得到解即是 A+p 和 A+\pi-p，其中 A 是直线旋转的角度，值为 \pi-\operatorname{atan2}(a,b)；p 为水平线与单位圆在 y 轴右边交点的圆心角，值为 \arcsin(\frac{|c|}{\sqrt{a^2+b^2}})。

解方程部分代码：

bool Samed(double a,double b){
    return fabs(a-b)<eps;
}
double lim(double r){
    while(r<-pi) r+=2*pi;
    while(r>pi) r-=2*pi;
    return r;
}
vector<double> Solve(double a,double b,double c){//a*cosx+b*sinx+c=0
    if(Samed(a,0)&&Samed(b,0)) return {};
    double d=c/sqrt(a*a+b*b);
    if(d<-1||d>1) return {};
    double q=asin(d),A=pi-atan2(a,b);
    double ans1=lim(A+q),ans2=lim(A+pi-q);
    if(Samed(ans1,ans2)) return {ans1};
    else return {ans1,ans2};
}

完整代码

#include<bits/stdc++.h>
using namespace std;
const double pi=acos(-1);
const double eps=1e-9;
bool Samed(double a,double b);
struct Root;
int x,y,r,xx,yy,rr;
vector<Root> roots;
struct Vec2{
    double x,y;
    Vec2(){}
    Vec2(double X,double Y):x(X),y(Y){}
    Vec2 operator + (const Vec2 &v)const{
        return Vec2(x+v.x,y+v.y);
    }
};
struct Root{
    double sx,sy,tx,ty,len;
    bool operator < (const Root &r)const{
        if(!Samed(sx,r.sx)) return sx<r.sx;
        if(!Samed(sy,r.sy)) return sy<r.sy;
        if(!Samed(tx,r.tx)) return tx<r.tx;
        return ty<r.ty;
    }
};
double Dis(Vec2 a,Vec2 b){
    return sqrt((a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y));
}
bool Samed(double a,double b){
    return fabs(a-b)<eps;
}
Root GetRoot(double a,double b){
    Vec2 v1(x+r*cos(a),y+r*sin(a)),v2(xx+rr*cos(b),yy+rr*sin(b));
    return {
        v1.x,v1.y,
        v2.x,v2.y,
        Dis(v1,v2)
    };
}
double lim(double r){
    while(r<-pi) r+=2*pi;
    while(r>pi) r-=2*pi;
    return r;
}
vector<double> Solve(double a,double b,double c){//a*cosx+b*sinx+c=0
    if(Samed(a,0)&&Samed(b,0)) return {};
    double d=c/sqrt(a*a+b*b);
    if(d<-1||d>1) return {};
    double q=asin(d),A=pi-atan2(a,b);
    double ans1=lim(A+q),ans2=lim(A+pi-q);
    if(Samed(ans1,ans2)) return {ans1};
    else return {ans1,ans2};
}
int main(){
    while(true){
        scanf("%d %d %d %d %d %d",&x,&y,&r,&xx,&yy,&rr);
        if(!x&&!y&&!r&&!xx&&!yy&&!rr) break;
        roots.clear();
        if(x==xx&&y==yy&&r==rr){
            puts("-1");
            continue;
        }
        vector<double> ans1=Solve(x-xx,y-yy,r+rr);
        vector<double> ans2=Solve(x-xx,y-yy,r-rr);
        for(double ans:ans1) roots.push_back(GetRoot(ans,pi+ans));
        for(double ans:ans2) roots.push_back(GetRoot(ans,ans));
        sort(roots.begin(),roots.end());
        printf("%d\n",(int)roots.size());
        for(Root root:roots){
            printf("%.6f %.6f %.6f %.6f %.6f\n",root.sx,root.sy,root.tx,root.ty,root.len);
        }
    }
}