自动搬运

查看原文

来自洛谷，原作者为

	_Goodnight AFOed.

搬运于2025-08-24 22:03:20，当前版本为作者最后更新于2021-11-15 12:56:20，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

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

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

}