import java.util.ArrayList; import java.util.HashSet; import java.util.LinkedList; import java.util.Queue; import java.util.Scanner; import java.util.Set; public class Wheels { Scanner in = new Scanner(System.in); // List of wheel objects storing necessary data ArrayList list; // list.get(i) is the indices of wheels adjacent to wheel i public static void main(String[] args) { Wheels x = new Wheels(); x.input(); } public class Wheel { // Wheel location and size int x, y, r; // Unique identifier for read-in order int index; // Numerator and denominator of speed int p, q; // Boolean for rotation direction boolean clockwise; // List of indices of adjacent wheels (adjacency list) ArrayList adjacents; // Constructor public Wheel(int tx, int ty, int tr, int tIndex, int tp) { x = tx; y = ty; r = tr; index = tIndex; p = tp; q = 1; clockwise = true; adjacents = new ArrayList(); } } private void input() { // Number of test cases int T = in.nextInt(); for (int i = 0; i < T; i++) { // Number of wheels for this test case int n = in.nextInt(); // Clear data for each test case list = new ArrayList(); for (int j = 0; j < n; j++) { int x = in.nextInt(); int y = in.nextInt(); int r = in.nextInt(); int p; if (j == 0) { p = 1; } else { p = 0; } list.add(new Wheel(x, y, r, j, p)); } // Populate adjacency lists for (int j = 0; j < n; j++) { for (int k = j+1; k < list.size(); k++) { int dx = list.get(j).x - list.get(k).x; int dy = list.get(j).y - list.get(k).y; int r2 = list.get(j).r + list.get(k).r; if ((dx*dx + dy*dy) == (r2*r2)) { // TODO: may need to create list from scratch every time list.get(j).adjacents.add(k); list.get(k).adjacents.add(j); } } } // BFS starting from first wheel BFS(0); // Print statements for (int j = 0; j < n; j++) { int p = list.get(j).p; int q = list.get(j).q; boolean clockwise = list.get(j).clockwise; if (p == 0) { System.out.println("not moving"); } else { System.out.print(p + "/" + q); if (clockwise) { System.out.println(" clockwise"); } else { System.out.println(" counterclockwise"); } } } } } // Helper method to implement BFS private void BFS(int root) { Queue Q = new LinkedList(); Set visited = new HashSet(); visited.add(root); Q.add(root); while (! Q.isEmpty()) { int cur = Q.remove(); for (int i: list.get(cur).adjacents) { if (! visited.contains(i)) { visited.add(i); Q.add(i); calcSpeed(cur, i); } } } } // Helper method for calculating output speed private void calcSpeed(int cur, int next) { // Access radiuses for current and next wheels int r1 = list.get(cur).r; int r2 = list.get(next).r; int p1 = list.get(cur).p; int q1 = list.get(cur).q; // Calculate next wheel speeds int p2 = r1*p1; int q2 = r2*q1; // Calculate GCD of next wheel speeds int GCD = euclid(p2, q2); // Define motion parameters of next wheel list.get(next).p = p2 / GCD; list.get(next).q = q2 / GCD; list.get(next).clockwise = (! list.get(cur).clockwise); } // Euclid's algorithm for computing the GCD of 2 integers (recursive) private int euclid(int p, int q) { // Base case if (q == 0) return p; // Reduction step return euclid(q, p % q); } }