// CCC2006s3TinCanTelephoneVector // // this vector solution is by Jason Jackson of Aurora high School // Explaination: (if the reader has a better explaination, please tell me) // In vector speak: // a-b is a vector from b to a // a.b is the (length of the projection of a onto b) * (length of b) // // wrt the dot product, it is its sign which is important: // if the two vectors a and b are placed end to end, the dot product of 0 // indicates they are at right angles and if its positive they form // an acute angle. (REMEMBER that!) // // The problem is to see if a series of corners // defining a building intersect the line segment from r to j. // // so r and j are the main endpoints r-j (or j-r) is the main vector // c is a corner of the building // w is vector going at right angles to c from the projection of c // onto the r-j line. (got that: w goes AWAY from the main line) // // So where is c with regard to the main segment? // there are 3 choices: its ON the line or "inside" or "outside". // "Inside" means that the vectors FROM r to c and j are acute as well // as the vectors FROM J to c and r. Or more simply, // the projection of c onto the line rj actually hits BETWEEN r and j import java.awt.*; import hsa.*; public class CCC2006s3TinCanTelephoneVector { static Console console; public static void main (String[] args) { console = new Console (); TextInputFile f = new TextInputFile ("s3.1.in"); Vector r, j, c, w, l, csj; int n, corners, touching; boolean outside, collision; r = new Vector (f.readDouble (), f.readDouble ()); j = new Vector (f.readDouble (), f.readDouble ()); n = f.readInt (); touching = 0; for (int i = 0 ; i < n ; i++) { outside = true; collision = false; corners = f.readInt (); l = new Vector (); for (int k = 0 ; k < corners ; k++) { c = new Vector (f.readDouble (), f.readDouble ()); csj = c.subtract (j); w = csj.subtract (csj.projection (r.subtract (j))); // is the projection of c onto the line rj, BETWEEN r and j? // if yes, its inside (ie not outside) if (r.subtract (j).dot (csj) > 0 && j.subtract (r).dot (c.subtract (r)) > 0) outside = false; // w is the vector perpendicular FROM the rj line to c // if its magnitude is zero its ON the line // or if the old w (l) and w form an obtuse angle that building's // side has crossed the rj line. if (w.magnitude () < 0.001 || w.dot (l) < 0) collision = true; l = w; } // if any point was inside and there was any collision at all // the building interferred with the tin can telephone if (!outside && collision) touching++; } console.println (touching); } } class Vector { protected double x, y; public Vector () { x = 0; y = 0; } public Vector (double x, double y) { this.x = x; this.y = y; } public String toString () { return "(" + x + "," + y + ")"; } public Vector add (Vector a) { return new Vector (x + a.x, y + a.y); } public Vector subtract (Vector a) { return new Vector (x - a.x, y - a.y); } public Vector multiply (double a) { return new Vector (a * x, a * y); } public double magnitude () { return Math.sqrt (x * x + y * y); } public double dot (Vector a) { return x * a.x + y * a.y; } public Vector projection (Vector a) { return a.multiply (dot (a) / (a.magnitude () * a.magnitude ())); } }