Tuesday, June 9, 2015

[LeetCode] Rectangle Area

Rectangle Area

Find the total area covered by two rectilinear rectangles in a 2D plane.
Each rectangle is defined by its bottom left corner and top right corner as shown in the figure.
Rectangle Area
Assume that the total area is never beyond the maximum possible value of int.
Credits:
Special thanks to @mithmatt for adding this problem, creating the above image and all test cases.
Solution:
The main observation is that the vertices of the common rectangle (if it exists) must be formed by x coordinates and y coordinates of the vertices of the given two rectangles.
There are 16 possible such vertices. For any of them, if it lies in both rectangles, then it is a vertex of the common rectangle. When the two rectangles are the same, all 16 of them belong to the common rectangle (each vertex is duplicated four times).
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
public class Solution {
   class Point {
       int x;
       int y;
       
       Point() { }
       
       Point(int _x, int _y) {
           x = _x;
           y = _y;
       }
   }
   
   class Rect {
       int left;
       int right;
       int top;
       int bottom;
       
       Rect() {}
       
       Rect(int l, int b, int r, int t) {
           left = l;
           bottom = b;
           right = r;
           top = t;
       }
       
       Rect(Point a, Point b, Point c, Point d) {
           left = min(a.x, b.x, c.x, d.x);
           bottom = min(a.y, b.y, c.y, d.y);
           right = max(a.x, b.x, c.x, d.x);
           top = max(a.y, b.y, c.y, d.y);
       }
       
       private int min(int v1, int v2, int v3, int v4) {
           int min12 = Math.min(v1, v2);
           int min34 = Math.min(v3, v4);
           return Math.min(min12, min34);
       }
       
       private int max(int v1, int v2, int v3, int v4) {
           int max12 = Math.max(v1, v2);
           int max34 = Math.max(v3, v4);
           return Math.max(max12, max34);
       }
       
       public boolean contains(Point pt) {
           return pt.x >= left && 
                  pt.x <= right && 
                  pt.y >= bottom && 
                  pt.y <= top;
       }
       
       public int area() {
           return (right - left) * (top - bottom);
       }
   }
   
   public int computeArea(
       int A, int B, int C, int D, 
       int E, int F, int G, int H
   ) {
       Rect rect1 = new Rect(A, B, C, D);
       Rect rect2 = new Rect(E, F, G, H);
       int[] x = new int[]{A, C, E, G};
       int[] y = new int[]{B, D, F, H};
       ArrayList<Point> vertices = new ArrayList<Point>();
       for (int i = 0; i < 4; i++) {
           for (int j = 0; j < 4; j++) {
               Point p = new Point(x[i], y[j]);
               if (rect1.contains(p) && rect2.contains(p)) {
                   vertices.add(p);
               }
           }
       }
       if (vertices.size() == 0 || vertices.size() == 1) {
           return rect1.area() + rect2.area();
       }
       if (vertices.size() == 16) {
           return rect1.area();
       }
       Rect rect_common = new Rect(
           vertices.get(0),
           vertices.get(1),
           vertices.get(2),
           vertices.get(3)
       );
       return rect1.area() - rect_common.area() + rect2.area();
   }
}
Posted by at

No comments:

Post a Comment

Subscribe to: Post Comments (Atom)