当前位置:首页 » 编程语言

leetcode_Rectangle Area

2015-08-06 19:51 本站整理 浏览(31)

描述:

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 * the maximum possible value of int.

思路:

1.本题目的意思是,求totalAreage=areage(A)||areage(B),就是求两个矩形的并集。

2.这题有点绕,解决问题的关键是求出两个矩形相交部分的面积,然后两个矩形的面积之和减去两个矩形相交的部分即是最后要求的结果

3.但是如何求两个矩形相交的部分呢,假设两个矩形相交,那就要求两个矩形相交部分的左边的最大值,右边的最小值,上边的最小值,下边的最大值

4.然后再根据矩形相交时的位置(比如左上右下方向,左下右上等来判断要减去的面积)

代码:

public int computeArea(int A, int B, int C, int D, int E, int F, int G,
			int H)
	{
		int totalArea = (D - B) * (C - A) + (H - F) * (G - E);
		int left, bottom, top, right;
		left = getLeft(A, E);
		bottom = getBottom(B, F);
		top = getTop(D, H);
		right = getRight(C, G);
		if(left<right&&bottom<top)//第一个矩形在第二个矩形的左方或下方
		{
			if(A<=E||B<=F)
			{
			    if(!(C<E&&D<F))
					totalArea -= (right - left) * (top - bottom);
			}
			if(E<A&&F<B)//第二个矩形在第一个矩形的左下方
			{
				if(!(G<A&&H<B))
					totalArea -= (right - left) * (top - bottom);
			}
		}
		return totalArea;
	}

	public int getLeft(int y1, int y2)
	{
		return y1 > y2 ? y1 : y2;
	}

	public int getBottom(int x1, int x2)
	{
		return x1 > x2 ? x1 : x2;
	}

	public int getTop(int x1, int x2)
	{
		return x1 < x2 ? x1 : x2;
	}

	public int getRight(int y1, int y2)
	{
		return y1 < y2 ? y1 : y2;
	}