LEET code -- 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.

Assume that the total area is never beyond the maximum possible value of int.

跟白癡一樣  一開始還想硬幹

但是太多Case要討論了

未完成的廢墟

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

int computeArea(int A, int B, int C, int D, int E, int F, int G, int H) { int left=abs( A-C )* abs(B-D); int right=abs(E-G)*abs(F-H); int middle=0; if(E>A && E<C && G>A && G<C){ //EFGH is in ABCD if(D>H && B>F){ //is upper middle=abs(B-H)*abs(E-G); }else if(H>D && F>B){ //is lower middle=abs(D-F)*abs(E-G); }else if(D>=H &&F>=B){ //is inside middle = right; }else middle=0; return left-middle+right; }else if(A>E && A<G && C>E && C<G){ //ABCD is in EFGH if(D>H && B>F){ //is upper middle=abs(B-H)*abs(A-C); }else if(H>D && F>B){ //is lower middle=abs(D-F)*abs(A-C); }else if(H>=D && B>=F){ //is inside middle = left; }else middle=0; return left-middle+right; }else if( E>A && E<C ){ //insert from right if(D>H && B>F){ //is upper middle=abs(B-H)*abs(E-C); }else if(H>D && F>B){ //is lower middle=abs(D-F)*abs(E-C); }else if(H>=D && B>=F){ //is inside middle = abs(H-F)*abs(E-C); }else middle=0; //int middle=abs(B-H)*abs(E-C); return left-middle+right; }else if( G>A && G<C ){ //insert from left if(D>=H && B>F){ //is upper middle=abs(B-H)*abs(G-A); }else if(H>D && F>B){ //is lower middle=abs(D-F)*abs(G-A); }else if(H>=D && B>=F){ //is inside middle = abs(D-F)*abs(G-A); }else middle=0; //int middle=abs(B-H)*abs(G-A); return left-middle+right; }else if(E==A && G==C){ //maybe combin together if(D>=H && B>F){ //is upper middle=abs(B-H)*abs(E-C); }else if (H>D && F>B){ //is lower middle=abs(D-F)*abs(E-C); }else if(H>=D && B>=F){ //is inside middle = left; }else middle=0; //int middle=abs(B-H)*abs(E-C); return left-middle+right; }else{ //no interset return left+right; } }

_-----
解答

用數學去算

反正超過邊界的都一定不會重疊
接著 在去判斷 重疊時 哪條線會用到!!

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15

#define MIN(x,y)( ( (x)>=(y) )? (y):(x)) #define MAX(x,y)( ( (x)>=(y) )? (x):(y)) int computeArea(int A, int B, int C, int D, int E, int F, int G, int H) { int left=abs( A-C )* abs(B-D); int right=abs(E-G)*abs(F-H); if(E>=C || A>=G || B>=H ||F>=D)return left+right; // no intersection int width=abs( MIN(C,G)-MAX(A,E)); int heigh=abs( MAX(B,F) - MIN(D,H)); int middle=width*heigh; //printf("%d %d %d",left,middle,r) return left-middle+right; }