/* * Atlantis : Problem A from the Mid-Central European Regional Contest 2000 * of the ACM Programming contest. * * Given a set of rectangles with vertices of real (double) coordinates, * determine the total area the set of rectangles mutually cover. * * Parke Godfrey * 18 September 2008 */ import java.io.PrintStream; import java.util.*; /* * Rectangle : Holds a rectangle. */ class Rectangle implements Comparable { public final double xLow; public final double yLow; public final double xHigh; public final double yHigh; public final double area; public Rectangle(double xL, double yL, double xH, double yH) { xLow = xL; yLow = yL; xHigh = xH; yHigh = yH; area = (xHigh - xLow) * (yHigh - yLow); } // Whether the other rectangle overlaps with or touches this one. public boolean touches(Rectangle other) { if ( ((this.xLow <= other.xLow) && (this.xHigh >= other.xLow) && (this.yLow <= other.yLow) && (this.yHigh >= other.yLow)) || ((this.xLow <= other.xLow) && (this.xHigh >= other.xLow) && (this.yLow <= other.yHigh) && (this.yHigh >= other.yHigh)) || ((this.xLow <= other.xHigh) && (this.xHigh >= other.xHigh) && (this.yLow <= other.yLow) && (this.yHigh >= other.yLow)) || ((this.xLow <= other.xHigh) && (this.xHigh >= other.xHigh) && (this.yLow <= other.yHigh) && (this.yHigh >= other.yHigh)) ) { return true; } else { return false; } } public int compareTo(Object obj) { Rectangle other = (Rectangle) obj; if (this.area > other.area) { return -1; } else if (this.area < other.area) { return 1; } else { return 0; } } } public class RectCover { private static Stack frag = new Stack(); private static void fragment(Rectangle base) { if (!frag.empty()) { Rectangle box = frag.pop(); // Take a box to check. fragment(base); // Handle rest of stack. // Check if the boxes do not overlap or even touch. if (!base.touches(box)) { frag.push(box); // Put it back. return; } // We overlap (or touch). So add any pieces that result // from trimming base away from box. if (box.yLow < base.yLow) { Rectangle piece = new Rectangle( box.xLow, box.yLow, box.xHigh, base.yLow ); frag.push(piece); } if (box.yHigh > base.yHigh) { Rectangle piece = new Rectangle( box.xLow, base.yHigh, box.xHigh, box.yHigh ); frag.push(piece); } if (box.xLow < base.xLow) { Rectangle piece = new Rectangle( box.xLow, Math.max(box.yLow, base.yLow), base.xLow, Math.min(box.yHigh, base.yHigh) ); frag.push(piece); } if (box.xHigh > base.xHigh) { Rectangle piece = new Rectangle( base.xHigh, Math.max(box.yLow, base.yLow), box.xHigh, Math.min(box.yHigh, base.yHigh) ); frag.push(piece); } // If no pieces, the box was contained by the base rectangle. } } public static void main(String[] args) { Scanner input = new Scanner(System.in); PrintStream output = System.out; int trial = 0; int rectNum = input.nextInt(); while (rectNum > 0) { trial++; // Read in the list of rectangles for this trial. Rectangle[] recArray = new Rectangle[rectNum]; for (int r = 0; r < rectNum; r++) { // Grab the next rectangle from input. recArray[r] = new Rectangle( input.nextDouble(), input.nextDouble(), input.nextDouble(), input.nextDouble() ); } Arrays.sort(recArray); // Now in descending order by size. double area = 0; // Keep a list of rectangles we need to clip against. Rectangle[] recCheck = new Rectangle[rectNum]; int checkEnd = 0; // Walk through the rectangles and clip each to find the area // each contributes to the overall area covered. for (int r = 0; r < rectNum; r++) { frag.push(recArray[r]); for (int c = 0; c < checkEnd; c++) { fragment(recCheck[c]); if (frag.empty()) break; } if (!frag.empty()) recCheck[checkEnd++] = recArray[r]; while (!frag.empty()) area += (frag.pop()).area; } // Print out the area for this trial. output.print("Test case #"); output.print(trial); output.println(""); output.print("Total explored area: "); output.printf("%.2f\n", area); output.println(""); rectNum = input.nextInt(); } } }