Final Exam Review Problems
Solutions
// Final Review Problem 1: // Yields true if this polyline does not cross itself public boolean noCross() { point u0,u1,v0,v1; for(int k=0;k< n;k++) { u0 = relVertex[k]; u1 = relVertex[k+1%n]; for(int j=k+2;j< n;j++) { v0 = relVertex[j]; v1 = relVertex[j+1%n] // Does the kth edge intersect the jth edge? if(point.intersect(u0,u1,v0,v1)) return false; } } return true; } // Final Review Problem 2: // Creates a quadrilateral with vertices P0, P1, P2, and P3 public closedPolyline(point P0, point P1, point P2, point P3) { n = 4; alpha = new point(0,0); relVertex = new point[4]; // If you look at all possible ways to connect the 4 points you discover that there // are only 3 possible 4-leg closed polylines: // P0P1P2P3, P0P1P3P2, and P0P2P1P3. // Must make sure that leg 0 and leg 2 do not cross and leg 1 and leg 3 do not cross. if(!point.intersect(P0,P1,P2,P3) && !point.intersect(P1,P2,P3,P0)) { // P0P1P2P3 is ok relVertex[0] = new point(P0); relVertex[1] = new point(P1); relVertex[2] = new point(P2); relVertex[3] = new point(P3); } else if(!point.intersect(P0,P1,P3,P2) && !point.intersect(P1,P3,P2,P0)) { // P0P1P3P2 is ok relVertex[0] = new point(P0); relVertex[1] = new point(P1); relVertex[2] = new point(P3); relVertex[3] = new point(P2); } else { // P0P2P1P3 is ok relVertex[0] = new point(P0); relVertex[1] = new point(P2); relVertex[2] = new point(P1); relVertex[3] = new point(P3); } } // Final Review Problem 3: // Yields true if a rook is threatened by a knight. public boolean seeHorsey() { for(int r=0;r< 8;r++) { for(int c=0;c< 8;c++) { if (pieceBoard[r][c].equals("R") && knightThreat[r][c]) { return true; } } } return false; } // Final Review Problem 4: // Yields the number of threatened red tiles public int redThreat() { int sum = 0; for(int r=0;r< 8;r++) { for(int c=0;c< 8;c++) { if (r+c%2==0 && threatBoard[r][c]) { sum++; } } } return sum; } // Yields true if at most one bishop on a red tile and at most one bishop // on a black tile. public int bishopNoBump() { int sumR = 0; int sumB = 0; for(int r=0;r< 8;r++) { for(int c=0;c< 8;c++) { if (r+c%2==0 && piece.Board[r][c].equals("B")) { sumR++; } if (r+c%2==1 && piece.Board[r][c].equals("B")) { sumB++; } if (sumR>1 || sumB>1) { return false; } } } return true; } // Final Review Problem 5: // Use the fact that if (x1,y1) and (x2,y2) are in the same quadrant then x1*x2 must // be positive and y1*y2 must be positive. double[][] A = T.getVertices(); boolean B = A[0][0]*A[1][0]>0 && A[0][1]*A[1][1] && A[0][0]*A[2][0]>0 && A[0][1]*A[2][1]>0; // Final Review Problem 6: boolean B = T1.Area()< T2.Area(); // Final Review Problem 7: int m = n*(n-1)*(n-2)/6; Triangle[] T = new Triangle[m]; int q=0; for(int i=0;i< n;i++) for(int j=i+1;j< n;j++) for(int k=j+1;k< n;k++) { T[q] = new Triangle(P[i],P[j],P[k]); q++; }