public int computeArea(int ax1, int ay1, int ax2, int ay2, int bx1, int by1, int bx2, int by2) {
int rect1 = rectangleArea(ax1, ay1, ax2, ay2);
int rect2 = rectangleArea(bx1, by1, bx2, by2);
int overlap = rectangleOverlapArea(new int[]{ax1, ay1, ax2, ay2}, new int[]{bx1, by1, bx2, by2});
return rect1-overlap+rect2;
}
private int rectangleArea(int ax1, int ay1, int ax2, int ay2) {
return (ax2-ax1) * (ay2-ay1);
}
public int rectangleOverlapArea(int[] rec1, int[] rec2) {
// 计算交集矩形的左下角和右上角
int x1 = Math.max(rec1[0], rec2[0]);
int y1 = Math.max(rec1[1], rec2[1]);
int x2 = Math.min(rec1[2], rec2[2]);
int y2 = Math.min(rec1[3], rec2[3]);
// 计算交集的宽度和高度
int width = x2 - x1;
int height = y2 - y1;
// 如果交集的宽度和高度都大于 0，说明有重叠
if (width > 0 && height > 0) {
return width * height;
}
// 没有重叠
return 0;
}
}
复制代码
效果
2ms 击败21.43%
小结
这种解法相对对比较天然。
v2-扫描线
思路
按照 x 轴，将整体的矩形面积，按照每一段 x 拆分为小矩形。
末了的和就是整体矩形之和。
解法
[code]public int computeArea(int ax1, int ay1, int ax2, int ay2, int bx1, int by1, int bx2, int by2) { int[][] arr = new int[2][]; arr[0] = new int[]{ax1, ay1, ax2, ay2}; arr[1] = new int[]{bx1, by1, bx2, by2}; Arrays.sort(arr, (o1, o2) -> o1[1] == o2[1] ? o1[3] - o2[3] : o1[1] - o2[1]); List xList = Arrays.asList(ax1, ax2, bx1, bx2); Collections.sort(xList); int ans = 0; for (int i = 1; i < 4; i++) { int width = xList.get(i) - xList.get(i-1); for (int[] ints : getLine(xList.get(i-1), xList.get(i), arr)) { ans += width * (ints[1] - ints[0]); } } return ans;}private List getLine(int x1, int x2, int[][] arr) { List list = new ArrayList(); for (int[] ints : arr) { if (x1 >= ints[0] && x2
