import java.util.Scanner; import java.util.Vector; import java.util.Random; public class AimItRight { static double distance_of_line_from_point(int x_1, int y_1, int x_2, int y_2, int x_0, int y_0) { double d1 = (double) Math.abs((x_2 - x_1)*(y_1 - y_0) - (x_1 - x_0)*(y_2 - y_1)); double d2 = Math.sqrt((double) ((x_2 - x_1)*(x_2 - x_1) + (y_2 - y_1)*(y_2 - y_1))); return d1/d2; } static double distance(int x_1, int y_1, int x_2, int y_2) { return Math.sqrt((double) ((x_2 - x_1)*(x_2 - x_1) + (y_2 - y_1)*(y_2 - y_1))); } private static int solveAimItRight(int point_a_x, int point_a_y, int point_b_x, int point_b_y, int radius) { /** Instantiate a set of mirrored tables. * * The main table has origin = (0, 0). * Tables are square and each side has length 100. * * A table (i, j) has origin at (100i, 100j). i and j may be negative. * */ Vector tables = new Vector(); for(int i = -10; i <= 10; i++) { for(int j = -10; j <= 10; j++) { if(Math.abs(i) + Math.abs(j) < 7) { int relative_bx = point_b_x * (i % 2 == 0 ? 1 : -1); int relative_by = point_b_y * (j % 2 == 0 ? 1 : -1); Table t = new Table(i*100, j*100, relative_bx, relative_by, Math.abs(i) + Math.abs(j)); tables.add(t); } } } int min = -1; /* Iterate over the tables. */ for(Table t1 : tables) { /* Construct the straight line between point A, and point B of t1. */ // System.out.println("====================================================================="); // t1.print(); // System.out.println("====================================================================="); boolean goes_into_hole = false; for(Table t2 : tables) { if(t2.num_rebounds <= t1.num_rebounds) { /* Compute the distance between the origin of t2 and the line between A and B of t1. */ double d = distance_of_line_from_point(point_a_x, point_a_y, t1.point_b_x, t1.point_b_y, t2.origin_coordinate_x, t2.origin_coordinate_y); // t2.print(); // System.out.println("The distance is " + d); /* Check if it is too small. */ if(d < (double) radius) { goes_into_hole = true; break; } } } if(! goes_into_hole) { /* We have a candidate. */ // System.out.print("We can hit point B in this table: "); // t1.print(); if((min == -1) || (min > t1.num_rebounds)) { min = t1.num_rebounds; } } } return min; } public static void main(String[] args) { /* Random rand = new Random(100); for(int ii = 0; ii < 200; ii++) { int a_x = -50 + rand.nextInt(100); int a_y = -50 + rand.nextInt(100); int b_x = -50 + rand.nextInt(100); int b_y = -50 + rand.nextInt(100); int radius = rand.nextInt(50); if( (distance(a_x, a_y, 0, 0) > (double) radius) && (distance(b_x, b_y, 0, 0) > (double) radius)) { System.out.println(a_x + " " + a_y + " " + b_x + " " + b_y + " " + radius); } } */ /* for(int a_x = -49; a_x < 49; a_x++) { System.out.println("========= " + a_x); for(int a_y = -49; a_y < 49; a_y++) { for(int b_x = -49; b_x < 49; b_x++) { for(int b_y = -49; b_y < 49; b_y++) { // System.out.println(a_x + " " + a_y + " " + b_x + " " + b_y); for(int i = 49; i > 20; i--) { if( (distance(a_x, a_y, 0, 0) > (double) i) && (distance(b_x, b_y, 0, 0) > (double) i)) { int ans = solveAimItRight(a_x, a_y, b_x, b_y, i); if(ans == -1) { // System.out.println("Not possible to hit point B from point A."); } else { if(ans > 4) { System.out.println("=================================================================== i = " + i); System.out.println("Possible to hit point B from point A within " + ans + " rebounds."); System.out.println(a_x + " " + a_y + " " + b_x + " " + b_y); } } } else { // System.out.println("Point A or point B are in the hole."); } } } } } } */ Scanner sc = new Scanner(System.in); int numCases = sc.nextInt(); for(int i = 0; i < numCases; i++) { int point_a_x = sc.nextInt(); int point_a_y = sc.nextInt(); int point_b_x = sc.nextInt(); int point_b_y = sc.nextInt(); int radius = sc.nextInt(); int ans = solveAimItRight(point_a_x, point_a_y, point_b_x, point_b_y, radius); if(ans == -1) { System.out.println("NOT POSSIBLE"); } else { System.out.println("REBOUNDS " + ans); } } } }