import java.util.*; import java.math.*; import java.io.*; import java.awt.*; import java.awt.geom.*; public class pool { static boolean Collision(double x1, double y1, double x2, double y2, double x, double y) { double d = Line2D.ptSegDist(x1,y1,x2,y2,x,y); if (d < 2-0.01) return true; if (d < 2+0.01) { System.err.println("Encountered a near miss with a ball."); } return false; } static boolean CanHit(Point2D.Double cue, Point2D.Double target, Point2D.Double pocket, Point2D.Double[] balls) { if (target.distance(pocket) < 0.01) { System.err.println ("Encountered a test case in which target and pocket are very close to each other."); } // compute direction vector from pocket to target ball double dx = (target.x - pocket.x) / target.distance(pocket); double dy = (target.y - pocket.y) / target.distance(pocket); // compute final position of cue ball double fx = target.x + 2*dx, fy = target.y + 2*dy; if (Math.abs(cue.x - fx) < 0.01 && Math.abs(cue.y - fy) < 0.01) { System.err.println ("Encountered a test case in which old and new position of cue ball are very close to each other."); } // compute direction vector from final cue position to original cue position double Dx = cue.x - fx; double Dy = cue.y - fy; double D = Math.sqrt(Dx*Dx + Dy*Dy); Dx /= D; Dy /= D; double angle = Math.abs(Math.acos(-Dx * dx - Dy * dy)); if (angle < Math.PI/2 - 0.01) return false; if (angle < Math.PI/2 + 0.01) { System.err.println ("Encountered a test case in which angle is very close to ninety."); } // check for ball collisions for (int i = 0; i < balls.length; i++) { if (Collision(cue.x, cue.y, fx, fy, balls[i].x, balls[i].y)) return false; if (Collision(target.x, target.y, pocket.x, pocket.y, balls[i].x, balls[i].y)) return false; } return true; } static void FindShots(Point2D.Double cue, Point2D.Double target, Point2D.Double[] balls) { double px[] = { 0, 54, 108, 0, 54, 108 }; double py[] = { 0, 0, 0, 54, 54, 54 }; int pockets_hit = 0; for (int p = 0; p < 6; p++) { if (CanHit(cue, target, new Point2D.Double(px[p], py[p]), balls)) { if (pockets_hit > 0) System.out.print(" "); System.out.print("" + (p+1)); pockets_hit++; } } if (pockets_hit == 0) System.out.print("no shot"); System.out.println(); } public static void main(String[] args) { Scanner s = new Scanner(System.in); while (true) { Point2D.Double cue = new Point2D.Double(); Point2D.Double target = new Point2D.Double(); cue.x = s.nextDouble(); if (cue.x == 0) break; cue.y = s.nextDouble(); target.x = s.nextDouble(); target.y = s.nextDouble(); int n = s.nextInt(); Point2D.Double[] balls = new Point2D.Double[n]; for (int i = 0; i < n; i++) { balls[i] = new Point2D.Double(); balls[i].x = s.nextDouble(); balls[i].y = s.nextDouble(); } FindShots(cue, target, balls); } } }