未分類

Rectangle Area

Go, LeetCode, Math

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.

提示 解題應用
Math 規律觀查

Default:

1
2
3
func computeArea(A int, B int, C int, D int, E int, F int, G int, H int) int {
}

解答思路:

要算出一平面上兩個矩形所圍出的面積，當然就是分別將兩個的長與寬相乘後做相加，然而如果兩個矩形發生重疊的話將會導致該塊面積重覆做計算，因此萬一有重疊的話就必需要算出重疊的面積然後將其減去，至於要找出重疊面積的長與寬，以範例的圖來說，仔細觀查會發現到重疊部分左邊的邊其X軸的位置會是E，因為E比A大，但如果是下圖的話:

左邊的X軸位置會是A，因為A比E大，因此要找左邊的X軸就是比較A與E誰大，反之要找右邊的X軸就是比較C與G誰小，同理要找下方的Y軸就是比較B與F誰大，上方的Y軸就是比較D與H誰小，有了各邊的X軸與Y軸位置自然可以得出四個點座標，甚至可以推出該重疊面積，最後只要判斷右邊是否比左邊的X軸位置大，上方是否比下方的Y軸位置大就可以得知兩矩形是否產生重疊，進而決定是否要減去重疊的面積。

程式碼解說:

如思路所述，先分別將兩個矩形的長與寬相乘後做相加，再求重疊矩形的相對位置，其中重疊矩形左邊的X軸就是比較A與E誰大，右邊的X軸就是比較C與G誰小，下方的Y軸就是比較B與F誰大，上方的Y軸就是比較D與H誰小，最後只要判斷右邊是否比左邊的X軸位置大，上方是否比下方的Y軸位置大就可以得知兩矩形是否產生重疊，進而決定是否要減去重疊的面積

1
2
3
4
5
6
7
8
9
10
11
func computeArea(A int, B int, C int, D int, E int, F int, G int, H int) int {
	area := (C-A)*(D-B) + (G-E)*(H-F)
	left := max(A, E)
	right := min(C, G)
	bottom := max(B, F)
	top := min(D, H)
	if right > left && top > bottom {
		return area - (right-left)*(top-bottom)
	}
	return area
}

這部分就只是單純實作了比較兩個值的大小，並回傳對應的大小值

1
2
3
4
5
6
7
8
9
10
11
12
func max(a int, b int) int {
	if a > b {
		return a
	}
	return b
}
func min(a int, b int) int {
	if a < b {
		return a
	}
	return b
}

完整程式碼:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
func computeArea(A int, B int, C int, D int, E int, F int, G int, H int) int {
	area := (C-A)*(D-B) + (G-E)*(H-F)
	left := max(A, E)
	right := min(C, G)
	bottom := max(B, F)
	top := min(D, H)
	if right > left && top > bottom {
		return area - (right-left)*(top-bottom)
	}
	return area
}
func max(a int, b int) int {
	if a > b {
		return a
	}
	return b
}
func min(a int, b int) int {
	if a < b {
		return a
	}
	return b
}

總結:

要算出一平面上兩個矩形所圍出的面積，先分別將兩個矩形的長與寬相乘後做相加，再藉由兩矩形的頂點座標進而推出重疊矩形的相對位置(座標)，最後透過重疊矩形的相對位置來判斷是否產生重疊，並決定是否要減去重疊的面積(細節請參考解答思路)。

分享到