import java.io.*; import java.util.*; import java.awt.*; import java.text.*; import java.math.*; /** * Solution to Pool Table * * This solution won't try to compute reflections. Instead, it'll set up * a coordinate system of reflected pool tables, like this: * * +-------+-------+-------+-------+ * | t | t | t | t | * | | | | | * +-------+-------+-------+-------+ * | | | | | * | t | t | t | t | * +-------+=======+-------+-------+ * | t [ T ] t | t | * | [ C ] | | * +-------+=======+-------+-------+ * | | | | | * | t | t | t | t | * +-------+-------+-------+-------+ * * Here, C is the Cue, T is the Target, and the t's represent the Target's image * in reflections of the pool table. * * So, if we have to bounce off 5 edges before hitting the target, then we look at * the reflection of the table that's 5 up and 0 over, and then 4 up and 1 over, * 3 up and 2 over, and so on. We have to go all the way around, so we also have * to check -2 up and 3 over, 1 up and -4 over, and so on. Then, we have to check * lesser reflections, to see of there's any reflection of the Target that's between * our desired Target and the Cue, meaning that the Cue would hit the Target before * hitting the required number of Edges. */ class pooltable { public Scanner sc; public PrintStream ps; public String toString() { return "pooltable"; } /** * Distance between two points (x1,y1) and (x2,y2). * * @param x1 * @param y1 * @param x2 * @param y2 * @return The distance between (x1,y1) and (x2,y2) */ public double distance( int x1, int y1, int x2, int y2 ) { double dx = x2-x1; double dy = y2-y1; return Math.sqrt( dx*dx + dy*dy ); } /** * Determine if points (ax,ay), (bx,by) and (cx,cy) lie on the same line. * * @param ax * @param ay * @param bx * @param by * @param cx * @param cy * @return true if (ax,ay), (bx,by) and (cx,cy) lie on the same line, otherwise false */ public boolean collinear( int ax, int ay, int bx, int by, int cx, int cy ) { boolean result = false; if( ay==by ) { // Check if they all have the same Y coord result = (by==cy); } else if( ax==bx ) { // Check if they all have the same X coord result = (bx==cx); } else { // They're collinear if A-B has the same slope as B-C // // by-ay cy-by // That is, ----- = ----- // bx-ax cx-bx // // Cross multiply so we can keep things all in integers, and we get this: result = ((by-ay)*(cx-bx) == (cy-by)*(bx-ax)); } return result; } /** * Determine if point (x2,y2) lies between points (x1,y1) and (x3,y3). * * @param x1 * @param y1 * @param x2 * @param y2 * @param x3 * @param y3 * @return true if (x2,y2) lies between (x1,y1) and (x3,y3), otherwise false */ public boolean between( int x1, int y1, int x2, int y2, int x3, int y3 ) { // Is x2 between x1 and x3? boolean xbetween = (x1