TopCoder Problem Statement - Intersect

Give the area where a set of rectangles intersect.

01: public class Intersect { 02: 03: class Rectangle { 04: 05: final int left; // X coordinate of left edge 06: final int right; 07: final int top; // Y coordinate of top edge 08: final int bottom; 09: 10: public Rectangle(int x1, int y1, int x2, int y2) { 11: 12: /* 13: * We don't know if the first point is the top-left or bottom-right 14: * corner. But we can assign the left edge to the smaller of the 15: * x values, and the right edge to the larger. Same goes for top 16: * and bottom 17: */ 18: this.left = Math.min(x1, x2); 19: this.right = Math.max(x1, x2); 20: this.top = Math.max(y1, y2); 21: this.bottom = Math.min(y1, y2); 22: } 23: 24: /* 25: * Returns a rectangle that is the intersection of this rectangle 26: * and the paramter r. Returns null if there is no intersection. 27: */ 28: public Rectangle getIntersection(Rectangle r) { 29: 30: /* 31: * If the right edge of one rectangle is >= the left edge of the 32: * other, then there is no intersection. Return null. Same goes 33: * for the other three edges. 34: */ 35: if (r.left >= right) return null; 36: if (r.right <= left) return null; 37: if (r.top <= bottom) return null; 38: if (r.bottom >= top) return null; 39: 40: /* 41: * The intersection is given by the: 42: * right-most left edge 43: * highest bottom edge 44: * left-most right edge 45: * lowest top edge 46: */ 47: return new Rectangle( 48: Math.max(left, r.left), 49: Math.max(bottom, r.bottom), 50: Math.min(right, r.right), 51: Math.min(top, r.top)); 52: } 53: 54: public int getArea() { 55: return ((right - left) * (top - bottom)); 56: } 57: } 58: 59: public int area(int[] x, int[] y) { 60: 61: 62: /* 63: * Start with the largest possible rectangle. Then for each rectangle 64: * reduce it to the intersection. If the intersection is ever null, 65: * return 0. 66: */ 67: Rectangle common = null; 68: 69: for (int i=0; i < x.length - 1; i += 2) { 70: Rectangle r = new Rectangle(x[i], y[i], x[i+1], y[i+1]); 71: 72: if (common == null) { 73: common = r; 74: } else { 75: common = common.getIntersection(r); 76: if (common == null) return 0; 77: } 78: } 79: 80: return common.getArea(); 81: } 82: }

First, a Rectangle class is created to handle much of the work. This class provides a constructor, to take the input in a convenient manner; a method to get the Area of the Rectangle, and a method to return a new Rectangle that is the intersection of the current rectangle and the rectangle given as a parameter.

Then, we'll use a rectangle named common to represent the intersection of all the rectangles given. Initially, this gets set to the fist rectangle processed. Then with each additional rectangle, common becomes the intersection of itself and the new rectangle.

After all the input has been processed, return the area of the Rectangle common.

## No comments:

## Post a Comment