leetcode 3047. 求交集区域内的最大正方形面积 中等

在二维平面上存在n个矩形。给你两个下标从0开始的二维整数数组bottomLeft和topRight，两个数组的大小都是n x 2，其中bottomLeft[i]和topRight[i]分别代表第i个矩形的左下角和右上角坐标。

我们定义向右的方向为 x 轴正半轴（x 坐标增加），向左的方向为 x 轴负半轴（x 坐标减少）。同样地，定义向上的方向为 y 轴正半轴（y 坐标增加），向下的方向为 y 轴负半轴（y 坐标减少）。

你可以选择一个区域，该区域由两个矩形的交集形成。你需要找出能够放入该区域内的最大正方形面积，并选择最优解。

返回能够放入交集区域的正方形的最大可能面积，如果矩形之间不存在任何交集区域，则返回0。

示例 1：

输入：bottomLeft = [[1,1],[2,2],[3,1]], topRight = [[3,3],[4,4],[6,6]]输出：1解释：边长为 1 的正方形可以放入矩形 0 和矩形 1 的交集区域，或矩形 1 和矩形 2 的交集区域。因此最大面积是边长 * 边长，即 1 * 1 = 1。 可以证明，边长更大的正方形无法放入任何交集区域。

示例 2：

输入：bottomLeft = [[1,1],[2,2],[1,2]], topRight = [[3,3],[4,4],[3,4]]输出：1解释：边长为 1 的正方形可以放入矩形 0 和矩形 1，矩形 1 和矩形 2，或所有三个矩形的交集区域。因此最大面积是边长 * 边长，即 1 * 1 = 1。 可以证明，边长更大的正方形无法放入任何交集区域。 请注意，区域可以由多于两个矩形的交集构成。

示例 3：

输入：bottomLeft = [[1,1],[3,3],[3,1]], topRight = [[2,2],[4,4],[4,2]]输出：0解释：不存在相交的矩形，因此，返回 0 。

提示：

• n == bottomLeft.length == topRight.length
• 2 <= n <= 10^3
• bottomLeft[i].length == topRight[i].length == 2
• 1 <= bottomLeft[i][0], bottomLeft[i][1] <= 10^7
• 1 <= topRight[i][0], topRight[i][1] <= 10^7
• bottomLeft[i][0] < topRight[i][0]
• bottomLeft[i][1] < topRight[i][1]

分析：检查任意两个矩形是否相交，如果相交，取横向、纵向相交部分的较小值作为正方形的边，最后返回边长相乘的值。

判断两个区间是否有重合部分，可以先分别计算两个区间的长度，如果区间长度之和大于右端点的最大值减去左端点的最小值的差大于 0，说明重合。

long long largestSquareArea(int** bottomLeft, int bottomLeftSize, int* bottomLeftColSize, int** topRight, int topRightSize, int* topRightColSize) { int n=bottomLeftSize,ans=0; for(int i=0;i<n;++i) { int len_xi=topRight[i][0]-bottomLeft[i][0],len_yi=topRight[i][1]-bottomLeft[i][1]; for(int j=i+1;j<n;++j) { int len_xj=topRight[j][0]-bottomLeft[j][0],len_yj=topRight[j][1]-bottomLeft[j][1]; int l1=len_xi+len_xj-(fmax(topRight[i][0],topRight[j][0])-fmin(bottomLeft[i][0],bottomLeft[j][0])); int l2=len_yi+len_yj-(fmax(topRight[i][1],topRight[j][1])-fmin(bottomLeft[i][1],bottomLeft[j][1])); ans=fmax(ans,fmin(l1,l2)); } } return 1LL*ans*ans; }