bzoj#P4050. [Cerc2014] Wheels

[Cerc2014] Wheels

题目描述

平面上有 nn 个齿轮,每个齿轮可以看作为一个圆,它们没有重叠,但可以相切。

如果两个齿轮相切,则其中一个齿轮转动,则另外一个更着转动。

当用每分钟转一圈的速度推动 11 号齿轮时,求每个齿轮的转速,假定机器不会卡死。

输入格式

第一行一个整数 TT 表示数据组数。

每一组数据的第一行是一个整数 nn 表示有 nn 个齿轮。

接下来的 nn 行,每行三个整数 x,y,rx,y,r 表示一个以 (x,y)(x,y) 为圆心,半径为 rr 的齿轮。

输出格式

对于每一组数据输出 nn 行,第 ii 行表示第 ii 个齿轮的转速。

对于可以转动的齿轮,输出一个形如 p/q 的不可约分分数,然后输出 clockwise 或者 counterclockwise 表示顺时针或逆时针。

对于不可转动的齿轮,输出 not moving 表示这个齿轮无法转动。

1
5
0 0 6
6 8 4
-9 0 3
6 16 4
0 -11 4

1 clockwise
3/2 counterclockwise
2 counterclockwise
3/2 clockwise
not moving

数据规模与约定

对于 100%100\% 的数据,1n1031\le n \le 10^3104x,y104 -10^4 \le x, y \le 10^41r1041 \le r \le 10^4