建议学图形学之前，先搞完计算几何

路径:
(解析几何，线性代数，群论)->计算几何->图形学

这个圆相切，虽然简单。但是用的地方还挺多的。
比如计算几何，图形学，游戏, CAD/CAM等。
很简单但是非常重要，所以值得讲一下。

如图所示，很明显，只要判断 |AC| = R1 + R2 即可
相等就是两圆相切

代码为:

struct Circle{
    int x;
    int y;
    int r;
};

bool isTangent(Circle& a,Circle& b){
    int dis = (a.x - b.x) * (a.x - b.x) + (a.y - b.y) * (a.y - b.y);
    int rsum = a.r + b.r;
    return dis == rsum * rsum;
}

三维的同理

判断球相交或者相切

struct Ball{
    i64 x,y,z.r;
};

bool isTangen(Ball& a,Ball& b){
    i64 dist = (a.x - b.x) * (a.x - b.x) + 
              (a.y - b.y) * (a.y - b.y) +
              (a.z - b.z) * (a.z - b.z);
    i64 sum = a.r + b.r;
    return dist <= sum * sum;
}

例题 1: P2903 [USACO08MAR]The Loathesome Hay Baler S

齿轮要能传动，则圆必须相切(这里是个近似计算，不考虑机械原理里的啮合角之类的)
传动比为 S*Rd/Rx

用一个GearWheel 来存齿轮对象。
题目要求的，就是一个速度的叠加。

那么bfs 即可

复杂度:
每次bfs 时，扫描整个数组
O(n^2)

#include<iostream>
#include<queue>

using namespace std;

const int MAXN = 1060;

//齿轮类
struct GearWheel{
    //齿轮中心坐标
    int x,y;
    //齿轮半径
    int r;
    //齿轮速度
    double speed;
    //传动能量，其实就是速度累加和
    double powerTrain;
};

GearWheel gearWheels[MAXN];
bool vis[MAXN];
int start;

int n,ex,ey;

//判断两个圆是否相切
bool isTangent(GearWheel& a,GearWheel& b){
    int dis = (a.x - b.x) * (a.x - b.x) + (a.y - b.y) * (a.y - b.y);
    int rsum = a.r + b.r;
    return dis == rsum * rsum;
}

void bfs(){
    queue<GearWheel> q;
    q.push(gearWheels[start]);
    vis[start] = true;
    while(!q.empty()){
        auto cur = q.front();
        q.pop();
        if(cur.x == ex && cur.y == ey){
            std::cout << (int)cur.powerTrain << endl;
            return;
        }
        for(int i = 1;i <= n;i++){
            if(vis[i] || !isTangent(cur,gearWheels[i])){
                continue;
            }
            vis[i] = true;
            gearWheels[i].speed = cur.speed * cur.r / gearWheels[i].r;
            gearWheels[i].powerTrain = gearWheels[i].speed + cur.powerTrain;
            q.push(gearWheels[i]);
        }
    }
}

int main(){
    cin >> n >> ex >> ey;
    for(int i = 1;i <= n;i++){
        cin >> gearWheels[i].x >> gearWheels[i].y >> gearWheels[i].r;
        if(gearWheels[i].x == 0 && gearWheels[i].y == 0){
            start = i;
            gearWheels[i].speed = 10000;
            gearWheels[i].powerTrain = 10000;
        }
    }
    bfs();
    return 0;
}

例题2：P3958 奶酪

代码如下:

#include<iostream>
#include<queue>
#include<cstring>

using namespace std;
using i64 = long long;

const int MAXN = 1005;

struct Ball{
    i64 x,y,z;
};

Ball balls[MAXN];

int beginPoints[MAXN];
int endPoints[MAXN];
int bidx;
int eidx;

int fa[MAXN];

int t;
i64 n,h,r;

void init(){
    bidx = eidx = 0;
    for(int i = 1;i <= n;i++){
        fa[i] = i;
    }
}

int find(int x){
    if(x == fa[x]){
        return x;
    }
    return fa[x] = find(fa[x]);
}

bool isTangen(Ball& a,Ball& b){
    i64 dist = (a.x - b.x) * (a.x - b.x) + 
              (a.y - b.y) * (a.y - b.y) +
              (a.z - b.z) * (a.z - b.z);
    return dist <= 4 * r * r;
}

int main(){
    cin >> t;
    while(t--){
        cin >> n >> h >> r;
        init();
        for(int i = 1;i <= n;i++){
            i64 x,y,z;
            cin >> x >> y >> z;
            balls[i] = {x,y,z};
            if(z + r >= h){
                endPoints[++eidx] = i;
            }
            if(z - r <= 0){
                beginPoints[++bidx] = i;
            }
        }

        for(int i = 1;i <= n;i++){
            for(int j = i + 1;j <= n;j++){
                int pi = find(i);
                int pj = find(j);
                if(pi == pj){
                    continue;
                }
                if(isTangen(balls[i],balls[j])){
                    fa[pi] = pj;
                }
            }
        }
        bool flag = false;
        for(int i = 1;i <= bidx;i++){
            for(int j = 1;j <= eidx;j++){
                if(find(beginPoints[i]) == find(endPoints[j])){
                    flag = true;
                    break;
                }
            }
            if(flag){
                break;
            }
        }
        std::cout << (flag ? "Yes" : "No") << endl;
    }
    return 0;
}