[LeetCode]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.

[LeetCode]Rectangle Area

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

题目大意:

计算二维平面上两个直线矩形的覆盖面积。

矩形通过其左下角和右上角的坐标进行定义。

假设总面积不会超过int的最大值。

解题思路:

简单计算几何。根据容斥原理:S(M ∪ N) = S(M) + S(N) - S(M ∩ N)

题目可以转化为计算矩形相交部分的面积

S(M) = (C - A) * (D - B)

S(N) = (G - E) * (H - F)

S(M ∩ N) = max(min(C, G) - max(A, E), 0) * max(min(D, H) - max(B, F), 0)

Python代码:

class Solution:
    # @param {integer} A
    # @param {integer} B
    # @param {integer} C
    # @param {integer} D
    # @param {integer} E
    # @param {integer} F
    # @param {integer} G
    # @param {integer} H
    # @return {integer}
    def computeArea(self, A, B, C, D, E, F, G, H):
        sums = (C - A) * (D - B) + (G - E) * (H - F)
        return sums - max(min(C, G) - max(A, E), 0) * max(min(D, H) - max(B, F), 0)

 

本文链接:http://bookshadow.com/weblog/2015/06/08/leetcode-rectangle-area/
请尊重作者的劳动成果,转载请注明出处!书影博客保留对文章的所有权利。

如果您喜欢这篇博文,欢迎您捐赠书影博客: ,查看支付宝二维码

Pingbacks已关闭。

暂无评论

张贴您的评论