1 import java.io.*; 2 import java.util.*; 3 import java.awt.*; 4 import java.text.*; 5 import java.math.*; 6 7 /** 8 * Solution to Pool Table 9 * 10 * This solution won't try to compute reflections. Instead, it'll set up 11 * a coordinate system of reflected pool tables, like this: 12 * 13 * +-------+-------+-------+-------+ 14 * | t | t | t | t | 15 * | | | | | 16 * +-------+-------+-------+-------+ 17 * | | | | | 18 * | t | t | t | t | 19 * +-------+=======+-------+-------+ 20 * | t [ T ] t | t | 21 * | [ C ] | | 22 * +-------+=======+-------+-------+ 23 * | | | | | 24 * | t | t | t | t | 25 * +-------+-------+-------+-------+ 26 * 27 * Here, C is the Cue, T is the Target, and the t's represent the Target's image 28 * in reflections of the pool table. 29 * 30 * So, if we have to bounce off 5 edges before hitting the target, then we look at 31 * the reflection of the table that's 5 up and 0 over, and then 4 up and 1 over, 32 * 3 up and 2 over, and so on. We have to go all the way around, so we also have 33 * to check -2 up and 3 over, 1 up and -4 over, and so on. Then, we have to check 34 * lesser reflections, to see of there's any reflection of the Target that's between 35 * our desired Target and the Cue, meaning that the Cue would hit the Target before 36 * hitting the required number of Edges. 37 */ 38 class pooltable 39 { 40 public Scanner sc; 41 public PrintStream ps; 42 43 public String toString() 44 { 45 return "pooltable"; 46 } 47 48 /** 49 * Distance between two points (x1,y1) and (x2,y2). 50 * 51 * @param x1 52 * @param y1 53 * @param x2 54 * @param y2 55 * @return The distance between (x1,y1) and (x2,y2) 56 */ 57 public double distance( int x1, int y1, int x2, int y2 ) 58 { 59 double dx = x2-x1; 60 double dy = y2-y1; 61 return Math.sqrt( dx*dx + dy*dy ); 62 } 63 64 /** 65 * Determine if points (ax,ay), (bx,by) and (cx,cy) lie on the same line. 66 * 67 * @param ax 68 * @param ay 69 * @param bx 70 * @param by 71 * @param cx 72 * @param cy 73 * @return true if (ax,ay), (bx,by) and (cx,cy) lie on the same line, otherwise false 74 */ 75 public boolean collinear( int ax, int ay, int bx, int by, int cx, int cy ) 76 { 77 boolean result = false; 78 79 if( ay==by ) 80 { 81 // Check if they all have the same Y coord 82 result = (by==cy); 83 } 84 else if( ax==bx ) 85 { 86 // Check if they all have the same X coord 87 result = (bx==cx); 88 } 89 else 90 { 91 // They're collinear if A-B has the same slope as B-C 92 // 93 // by-ay cy-by 94 // That is, ----- = ----- 95 // bx-ax cx-bx 96 // 97 // Cross multiply so we can keep things all in integers, and we get this: 98 result = ((by-ay)*(cx-bx) == (cy-by)*(bx-ax)); 99 } 100 101 return result; 102 } 103 104 /** 105 * Determine if point (x2,y2) lies between points (x1,y1) and (x3,y3). 106 * 107 * @param x1 108 * @param y1 109 * @param x2 110 * @param y2 111 * @param x3 112 * @param y3 113 * @return true if (x2,y2) lies between (x1,y1) and (x3,y3), otherwise false 114 */ 115 public boolean between( int x1, int y1, int x2, int y2, int x3, int y3 ) 116 { 117 // Is x2 between x1 and x3? 118 boolean xbetween = (x1<x3) ? (x1<=x2 && x2<=x3) : (x3<=x2 && x2<=x1); 119 120 // Is y2 between y1 and y3? 121 boolean ybetween = (y1<y3) ? (y1<=y2 && y2<=y3) : (y3<=y2 && y2<=y1); 122 123 // Are both coordinates in the right range, AND the points lie on the same line? 124 return xbetween && ybetween && collinear( x1, y1, x2, y2, x3, y3 ); 125 } 126 127 // Input parameters: w=width, l=length, (xc,yc)=Cue position, 128 // (xb,yb)=Target ball position, nbounces=number of times it must bounce off the edge. 129 public int w, l, xc, yc, xb, yb, nbounces; 130 131 // Remember the best (smallest) distance. This will be our final answer. 132 public double best; 133 134 /** 135 * Compute the X coordinate of the target ball on 136 * a reflected pool table that's 'over' over. 137 * 138 * @param over How many reflections over 139 * @return The x coordinate 140 */ 141 public int x( int over ) 142 { 143 return over*l + ((over&1)==0?xb:l-xb); 144 } 145 146 /** 147 * Compute the Y coordinate of the target ball on 148 * a reflected pool table that's 'up' up. 149 * 150 * @param over How many reflections up 151 * @return The y coordinate 152 */ 153 public int y( int up ) 154 { 155 return up*w + ((up&1)==0?yb:w-yb); 156 } 157 158 /** 159 * Check the reflection of the Target ball on a reflected pool table 160 * that's 'up' up and 'over' over. First, see if there are any lesser reflections 161 * that would get in the way. If not, compute the distance between 162 * the Cue and the reflected Target, and remember it if it's the smallest. 163 * 164 * @param up Number of reflected pool tables up 165 * @param over Number of reflected pool tables over 166 */ 167 public void check( int up, int over ) 168 { 169 // Compute (x,y) position of the Target ball's reflection here. 170 int xr = x(over); 171 int yr = y(up); 172 173 // Compute min and max of up and over. 174 // We'll iterate over all of these to try to find lesser reflections 175 // that block our path. 176 int uplo = Math.min( up, 0 ); 177 int uphi = Math.max( up, 0 ); 178 int overlo = Math.min( over, 0 ); 179 int overhi = Math.max( over, 0 ); 180 181 // Is the shot from the Cur to this reflection of the Target 182 // blocked by an earlier reflection of the Target? 183 boolean unblocked = true; 184 185 // Iterate over the entire space from [0,0] to [up,over]. 186 // Yeah, that's a lot more than you really need to check, but 187 // the numbers are small enough that it'll be fast enough, 188 // and we won't have to worry about debugging a tricky algorithm. 189 for( int u=uplo; u<=uphi && unblocked; u++ ) 190 for( int o=overlo; o<=overhi && unblocked; o++ ) 191 { 192 // Ignore the reflection that we're actually checking 193 if( u!=up || o!=over ) 194 { 195 // Does the Target reflection here block the path 196 // between the Cue and the Target reflection we're really interested in? 197 unblocked = !between( xc, yc, x(o), y(u), xr, yr ); 198 } 199 } 200 201 // If there's a clear shot 202 if( unblocked ) 203 { 204 // Remember this if it is the minimum distance we've seen so far. 205 best = Math.min( best, distance( xc, yc, xr, yr ) ); 206 } 207 } 208 209 public void doit() throws Exception 210 { 211 sc = new Scanner( System.in ); // new Scanner( new File( "pooltable.judge" ) ); 212 ps = System.out; // new PrintStream( new FileOutputStream( "pooltable.solution" ) ); 213 214 for(;;) 215 { 216 // Read Length and Width, exit if done. 217 l = sc.nextInt(); 218 w = sc.nextInt(); 219 if( l==0 || w==0 ) break; 220 221 // Read the rest of the input 222 xc = sc.nextInt(); 223 yc = sc.nextInt(); 224 xb = sc.nextInt(); 225 yb = sc.nextInt(); 226 nbounces = sc.nextInt(); 227 228 // Worst possible value for 'best' 229 best = Double.MAX_VALUE; 230 231 // Go through all possible values for 'up' 232 for( int up = 0; up<=nbounces; up++ ) 233 { 234 // up + over = nbounces 235 int over = nbounces - up; 236 237 // Check all four quadrants 238 check( up, over ); 239 check( -up, over ); 240 check( up, -over ); 241 check( -up, -over ); 242 } 243 244 // Print the answer 245 ps.printf( "%.3f", best ); 246 ps.println(); 247 } 248 } 249 250 public static void main(String[] args) throws Exception 251 { 252 long starttime = System.currentTimeMillis(); 253 new pooltable().doit(); 254 System.out.println( System.currentTimeMillis() - starttime ); 255 } 256 }