import java.util.ArrayList; import java.util.LinkedList; import java.util.PriorityQueue; import java.util.Scanner; public class Wheels { // always print 1 clockwise // adjacent circle // use euclids algorithm to find // use distance squared instead of distance // use bfs // create map from circle to its adjacents // hash code //int [][] [] data; Scanner in = new Scanner(System.in); public ArrayList> allWheels = new ArrayList<>(); public int numCases; /** * * data[0] is the array of circles adjacent to * circle 0. Each circle is int[3] * * @author danielmckee * */ public class Wheel { int x, y, r; int p, q; ArrayList adjacents; boolean isClock; boolean visited; public Wheel(int xcoor, int ycoor, int rad) { x = xcoor; y = ycoor; r = rad; adjacents = new ArrayList(); visited = false; } } //Wheel[] [] wdata; /** * wdata[0] is the array of circles * adjacent to circle 0. Each circle is Wheel * * @param args */ /*public Wheel[] adjacentTo(int i){ //return wdata[i]; return; }*/ public void findAllAdjacents (int idx) { // fill in for (Wheel a: allWheels.get(idx)) { for (Wheel b: allWheels.get(idx)) { if (a != b && isAdjacent(a, b)) { a.adjacents.add(b); } } } } public boolean isAdjacent (Wheel w1, Wheel w2) { int centDistsq = (int)Math.pow( (w2.x-w1.x) , 2 ) + (int)Math.pow( (w2.y-w1.y) , 2 ); int radiisq = (int)Math.pow( (w1.r+w2.r) , 2); if (centDistsq == radiisq) return true; return false; } public void solve() { for (int i= 0; i < numCases; i++) { findAllAdjacents(i); // fill in information we know about root (1st element of list) Wheel root = allWheels.get(i).get(0); root.isClock = true; root.p = 1; root.q = 1; root.visited = true; // solve from root solve(root); printOutput(i); } } private void printOutput(int i) { // TODO Auto-generated method stub for (Wheel w: allWheels.get(i)) { if (! w.visited) { System.out.println("not moving"); } else { String speed = w.p % w.q==0 ? Integer.toString(w.p/w.q) : Integer.toString(w.p) +"/" + Integer.toString(w.q); String dir = w.isClock ? "clockwise" : "counterclockwise"; System.out.println(speed + " " + dir); } } } public void solve(Wheel root) { // set root values if (root == null) return; for (Wheel w: root.adjacents) { if (!w.visited) { w.isClock = !(root.isClock); // speed root = p/q // new speed = p/q * rad(root)/rad(new) // to calculate speed: // newp = p*rad(root) // newq = q*rad(new) w.p = root.p*root.r; w.q = root.q*w.r; // reduce new p and q to lowest fraction int gcd = greatestCommonDenominator(w.p, w.q); w.p = w.p/gcd; w.q = w.q/gcd; w.visited = true; solve(w); } } } /** * GCD function taken from Kevin Kauffman's algorithm page * on speedyguy17.info * @param a * @param b * @return */ public int greatestCommonDenominator( int a, int b ){ while( b != 0 ){ int t = a%b; a = b; b = t; } return a; } public void readInput() { // TODO Auto-generated method stub numCases = in.nextInt(); for (int i = 0; i< numCases; i ++) { ArrayList aCase = new ArrayList<>(); int numwheels = in.nextInt(); for (int j = 0; j < numwheels; j++) { // read info for each wheel and add to aCase arraylist int x = in.nextInt(); int y = in.nextInt(); int r = in.nextInt(); Wheel w = new Wheel(x, y, r); aCase.add(w); } // add aCase array to allwheels arraylist allWheels.add(aCase); } } public static void main(String[] args) { Wheels wheelz = new Wheels(); wheelz.readInput(); wheelz.solve(); } }