无需数组循环的JavaScript彩色矩形覆盖面积求解方法

所有矩形以原点为中心且轴对齐，可利用对称性简化计算：只需计算第一象限内的并集面积，再乘以4得到总面积。

第一象限内的每个矩形可表示为从(0,0)到(a_i, b_i)的矩形，其中a_i = 矩形宽度/2，b_i = 矩形高度/2。计算第一象限并集面积的核心步骤：

1. 收集所有矩形的半宽a_i，去重后排序，得到分割x轴的关键点。
2. 遍历每两个相邻关键点组成的区间，找到能覆盖整个区间的矩形中最大的半高b_i，用区间宽度乘以该最大高度得到该区间的面积。
3. 累加所有区间的面积得到第一象限总面积，再乘以4即为最终结果。

function solve(N, arr) {
    if (N === 0) return 0;
    
    // 将每个矩形转换为第一象限的半宽和半高
    const rects = arr.map(([width, height]) => ({
        halfWidth: width / 2,
        halfHeight: height / 2
    }));
    
    // 收集所有半宽值，去重后加入0并排序，得到x轴分割点
    const halfWidths = new Set(rects.map(r => r.halfWidth));
    halfWidths.add(0);
    const sortedX = Array.from(halfWidths).sort((a, b) => a - b);
    
    let firstQuadArea = 0;
    
    // 遍历每个x区间计算面积
    for (let i = 0; i < sortedX.length - 1; i++) {
        const xStart = sortedX[i];
        const xEnd = sortedX[i + 1];
        const intervalWidth = xEnd - xStart;
        
        // 找到能覆盖当前区间的矩形的最大半高
        let maxHalfHeight = 0;
        for (const rect of rects) {
            if (rect.halfWidth >= xEnd) {
                maxHalfHeight = Math.max(maxHalfHeight, rect.halfHeight);
            }
        }
        
        firstQuadArea += intervalWidth * maxHalfHeight;
    }
    
    // 总面积为第一象限的4倍
    return firstQuadArea * 4;
}

1. 对称性处理：利用中心对称将问题缩小到第一象限，大幅减少计算量。
2. x轴分割：通过所有矩形的半宽值分割x轴，确保每个区间内的覆盖高度是固定的（即当前区间能覆盖的最大半高）。
3. 区间面积计算：对每个区间，找到能覆盖该区间的所有矩形中最高的那个，用区间宽度乘以高度得到该区间的贡献面积，累加后乘以4得到最终结果。

对于题目中的示例输入：

N=3
[8,2], [4,4], [2,6]

• 转换为第一象限的半宽半高：(4,1), (2,2), (1,3)
• 排序后的x分割点：[0,1,2,4]
• 各区间计算：
  • [0,1]：最大半高3 → 面积1*3=3
  • [1,2]：最大半高2 → 面积1*2=2
  • [2,4]：最大半高1 → 面积2*1=2
• 第一象限总面积7，乘以4得到28，与示例答案一致。

内容的提问来源于stack exchange，提问作者Pranav Kastury