import java.util.Scanner; import java.awt.Polygon; import java.util.PriorityQueue; import java.util.Comparator; import java.util.ArrayList; class Ball { public double x,y,dx,dy; public Ball(double x, double y, double dx, double dy) { this.x = x; this.y = y; this.dx = dx; this.dy = dy; } } class Event implements Comparable { public double time; public int ball; // which ball? public int poly; // which polygon? public int edge; // which edge? public double x,y; // where does the collision occur? public Event(double t, int b, int p, int e, double x, double y) { time = t; ball = b; poly = p; edge = e; this.x = x; this.y = y; } // Fixed this so, in case times tie, events are sorted by polygon public int compareTo(Event e) { if (this.time > e.time) return 1; else if (Math.abs(this.time - e.time)< 1e-7) return this.poly - e.poly; else return -1; } } public class Follow_BobR { public static Scanner in; public static int w,h,n,m,r,s; public static double l; public static Polygon[] poly; public static int q[]; public static Ball[] ball; public static PriorityQueue pq; public static final double EPS = 1e-7; public static void main(String[] args) { in = new Scanner(System.in); w = in.nextInt(); h = in.nextInt(); n = in.nextInt(); m = 1+in.nextInt(); // add 1 for bounding rectangle l = in.nextDouble(); r = in.nextInt(); s = in.nextInt(); ball = new Ball[n]; for (int i = 0; i < n; i++) ball[i] = new Ball(l,0,r,s); poly = new Polygon[m]; q = new int[m]; // countdown values // Add the bounding rectangle as one of the polygons: int x[] = new int[]{0,0,w,w}; int y[] = new int[]{0,h,h,0}; poly[0] = new Polygon(x,y,4); q[0] = Integer.MAX_VALUE; // bounding rectangle never goes away for (int i = 1; i < m; i++) { int p = in.nextInt(); x = new int[p]; y = new int[p]; for (int j = 0; j < p; j++) { x[j] = in.nextInt(); y[j] = in.nextInt(); } q[i] = in.nextInt(); poly[i] = new Polygon(x,y,p); } // Set up first n events (which may change as a result of other events): pq = new PriorityQueue(); for (int i = 0; i < n; i++) { Event e = update(i,i,0,3); pq.add(e); // "-1" since no previous bounce } simulate(); for (int i = 1; i < m-1; i++) { System.out.print(Math.max(0,q[i])+" "); } System.out.println(Math.max(0,q[m-1])); // postscript(); // prints a postscript image of the objects } //========================== // Returns null if ball b1 doesn't collide with polygon p1, else returns: // edge number containing the collision point in polygon p1 // (x,y) coordinates of the collison point // distance from ball b1 to collision point (x,y) // lastp and laste are used to exclude the current location of the ball, // which is always on the most recent collision edge //========================== public static double[] polycollide(int b1, int p1, int lastp, int laste) { Ball b = ball[b1]; Polygon p = poly[p1]; boolean found = false; // did we find a collision between b1 and p1? double mindist = Double.MAX_VALUE; // distance to nearest collision double minx = -1, miny = -1; // location of nearest collision int minedge = -1; // edge containing nearest collision // find a point outside the frame that lies on the ball's path: // (b.x + factor*b.dx, b.y + factor*b.dy) lies outside frame double factor = (w*w+h*h); for (int i = 0; i < p.npoints; i++) { if (p1==lastp && i==laste) continue; // we're already here! // do endpoints of edge i straddle the ball's path? double c1 = triple(b.x,b.y, b.x+factor*b.dx,b.y+factor*b.dy, p.xpoints[i],p.ypoints[i]); double c2 = triple(b.x,b.y, b.x+factor*b.dx,b.y+factor*b.dy, p.xpoints[(i+1)%p.npoints],p.ypoints[(i+1)%p.npoints]); if (c1*c2 >= 0) continue; // no // do endpoints of ball's path straddle the endpoints of edge i? c1 = triple(b.x,b.y, p.xpoints[i],p.ypoints[i], p.xpoints[(i+1)%p.npoints],p.ypoints[(i+1)%p.npoints]); c2 = triple(b.x+factor*b.dx,b.y+factor*b.dy, p.xpoints[i],p.ypoints[i], p.xpoints[(i+1)%p.npoints],p.ypoints[(i+1)%p.npoints]); if (c1*c2 >=0) continue; // no // yes, there is an intersection: find it: double ans[] = inter(b.x,b.y, b.x+factor*b.dx,b.y+factor*b.dy, p.xpoints[i],p.ypoints[i], p.xpoints[(i+1)%p.npoints],p.ypoints[(i+1)%p.npoints]); if (ans == null) System.out.println("Error--should be an intersection"); found = true; if (ans[2] < mindist) { mindist = ans[2]; minedge = i; minx = ans[0]; miny = ans[1]; } } if (!found) return null; return new double[]{minedge,minx,miny,mindist}; } //========================== // line segment intersection: // (x1,y1) is always the ball location; (x2,y2) is some point outside rect. // (x3,y3)--(x4,y4) is an edge of a polygon. // Returns (x,y) point of intersection and distance of this from (x1,y1). //========================== public static double[] inter(double x1, double y1, double x2, double y2, double x3, double y3, double x4, double y4) { double a1 = x2-x1; double b1 = x3-x4; double c1 = x3-x1; double a2 = y2-y1; double b2 = y3-y4; double c2 = y3-y1; double disc = a1*b2-a2*b1; // discriminant if (disc == 0) return null; // We find t1 and t2 for the parametric representation of the // intersection point (u,v) using Cramer's rule. // Here, u = double t1 = (c1*b2-c2*b1)/disc; double t2 = (a1*c2-a2*c1)/disc; double ans[] = new double[3]; ans[0] = x1+t1*a1; // parametric representation ans[1] = y1+t1*a2; // sanity check: if (Math.abs(ans[0] - x3 + t2*b1) > EPS || Math.abs(ans[1] - y3 + t2*b2) > EPS) { System.err.println("something funny in intersection"); System.err.printf("ans: (%f,%f); check (%f,%f)\n",ans[0],ans[1], (x3+t2*b1),(y3-t2*b2)); } ans[2] = Math.sqrt((x1-ans[0])*(x1-ans[0])+(y1-ans[1])*(y1-ans[1])); return ans; } //========================== // triple product -- for finding orientation of points with respect to a ray //========================== public static double triple(double x1, double y1, double x2, double y2, double x3, double y3) { return x1*y2 + x2*y3 + x3*y1 - x2*y1 - x1*y3 - x3*y2; } //========================== // Simulate the game. //========================== public static void simulate() { while (!pq.isEmpty()) { // Get next (set of) collisions: Event e = pq.poll(); ArrayList hold = new ArrayList(); // temporary holding while (!pq.isEmpty() && pq.peek().compareTo(e) == 0) { hold.add(pq.poll()); } // All these events are collisions with the same poly; if, collectively, // they reduce count to zero then lower the poly count and put back // all but the first one: if (q[e.poly] <= hold.size()+1) { q[e.poly] = 0; } for (Event eh:hold) { pq.add(eh); } // ...but is it REALLY a collision? Only if the q-value is 2 or more. if (q[e.poly] > 1) { // change ball's direction: bounce(e); // ball's new location is at the bounce point: ball[e.ball].x = e.x; ball[e.ball].y = e.y; q[e.poly]--; } else { // ...but we still have to update ball's position to this "ghost" // collision point: ball[e.ball].x = e.x; ball[e.ball].y = e.y; q[e.poly] = 0; } // Regardless of whether or not the collision actually occurred, need // to re-compute next event for this ball Event nexte = update(e.ball,e.time,e.poly,e.edge); // If ball hits bottom of frame, we're done with it; don't add a // new event: if (nexte.poly == 0 && nexte.edge == 3) { continue; } pq.add(nexte); } } //========================== // Change dx, dy values for a ball bouncing off an edge. // Formula: http://www.sdmath.com/math/geometry/reflection_across_line.html // (That give formula for reflection; just use the normal instead to get // bounce.) //========================== public static void bounce(Event e) { Polygon p = poly[e.poly]; double edx = (p.xpoints[(e.edge+1)%p.npoints]-p.xpoints[e.edge]); // edge dx double edy = (p.ypoints[(e.edge+1)%p.npoints]-p.ypoints[e.edge]); // edge dy double A = edx; double B = edy; double u = ((B*B-A*A)*(-ball[e.ball].dx) - 2*A*B*(-ball[e.ball].dy))/(A*A+B*B); double v = ((A*A-B*B)*(-ball[e.ball].dy) - 2*A*B*(-ball[e.ball].dx))/(A*A+B*B); ball[e.ball].dx = u; ball[e.ball].dy = v; } //========================== // For visualizing the layout--not part of solution: //========================== public static void postscript() { System.out.println("%!\n10 10 translate\n"); for (int i = 0; i < m; i++) { Polygon p = poly[i]; System.out.printf("%d %d moveto\n",10*p.xpoints[0],10*p.ypoints[0]); for (int j = 1; j < p.npoints; j++) { System.out.printf("%d %d lineto\n",10*p.xpoints[j],10*p.ypoints[j]); } System.out.println("closepath\nstroke\n"); } System.out.println("showpage"); } //========================== // Find earliest collision for ball ballnum after time t; since ball may // still be lying on the edge of a polygon (from previous collision), // use "lastp" and "laste" to eliminate this from consideration: //========================== public static Event update(int ballnum, double t, int lastp, int laste) { double earliest = Double.MAX_VALUE; // earliest event time for this ball int eb = -1, ep = -1, ee = -1; // earliest ball, polygon, edge double ex=-1, ey=-1; // earliest collision point // Check each polygon: for (int j = 0; j < m; j++) { if (q[j] <= 0) continue; // this poly is gon! double ans[] = polycollide(ballnum,j,lastp, laste); if (ans==null) { continue; } if (ans[3]+t < earliest) { // ans[3] = distance from ball to collison pt earliest = ans[3]+t; eb = ballnum; ep = j; ee = (int)ans[0]; ex = ans[1]; ey = ans[2]; } } Event e = new Event(earliest,eb,ep,ee,ex,ey); return e; } }