P4760 [CERC2014]Wheels

· · 题解

物理必修二，由线速度相等可推出下列式子

v_i=v_0*r_0/r_i

有了公式，思路就清晰了：对于每个轮子，我们都需要查看它是否带动与它相切的轮子是否已经被之前的轮子带动了，如果没有被带动，我们就把它带动起来，计算他的速度以及它的转动方向

注意： clockwise 顺时针

counterclockwise 逆时针

一个顺时针的齿轮 i 所带动的齿轮 j 是逆时针转的 这里可以用 clock 记录， -1 为暂时还未搜索到，也就时目前还没转动，然后用取反进行转向，用结构体存储每一个齿轮，每次搜索找到相切的并且没更新的，计算这个齿轮的速度。

然后我们就可以用广度优先搜索去找他啦

#include<bits/stdc++.h>
using namespace std;
#define INF 2000000000
typedef unsigned long long ull;
struct circle {
    int x=0, y=0, r=0;
    int clock = -1;
    int up = 1, down = 1;
    //0 shunshizhen -1 chushihua 1 nishizhen
}a[1010];
int n;
queue<circle> q;
//summary:
// 判断2圆是否相切
bool IsCircleQIE(circle a, circle b) {
    int d = (b.x - a.x) * (b.x - a.x) + (b.y - a.y) * (b.y - a.y);
    if (d <= (a.r + b.r)*(a.r+b.r)) {
        return 1;
    }
    return 0;
}
int gcd(int a, int b) { return b ? gcd(b, a % b) : a; }
pair<int, int> fenshu(int up, int down) {
    int d=gcd(up, down);
    return { up / d,down / d };
}
void read() {
        cin >> n;
        for (int i = 1; i <= n; i++) {
            cin >> a[i].x >> a[i].y >> a[i].r;
            a[i].clock = -1, a[i].up = a[i].down = 1;
        }
}
void out() {
    for (int i = 1; i <= n; i++) {
        if (a[i].clock != -1) {
            cout << a[i].up;
            if (a[i].down != 1) {
                cout << "/" << a[i].down;
            }
            cout << (a[i].clock==1 ? " counterclockwise" : " clockwise")<<endl;

        }
        else {
            cout << "not moving"<<endl;
        }
    }
}
int main() {
    int T;
    cin >> T;
    while (T--) {
        read();
        a[1].clock = 0;
        q.push(a[1]);
        while (!q.empty()) {
            circle u = q.front(); q.pop();
            for (int i = 1; i <= n; i++) {
                if (a[i].clock == -1) {
                    if (IsCircleQIE(u, a[i])) {
                        a[i].clock = !u.clock;
                        pair<int, int> t = fenshu(u.r * u.up, u.down * a[i].r);
                        a[i].up = t.first, a[i].down = t.second;
                        q.push(a[i]);
                    }
                }
            }
        }
        out();
    }

}