题目描述

实现一个简单的绘图模块，支持在二维坐标系中绘制和擦除矩形。对于给定的一系列操作，要求计算最终图形的面积。绘制操作（d）将新矩形添加到当前图形中并与已存在的矩形进行合并，而擦除操作（e）则会从当前图形中移除与指定矩形重叠的部分。求最终面积

思路分析

为了解决这个问题，我们采用扫描线算法和区间处理的思路。具体步骤如下：

1. 数据结构设计：

   • 使用一个列表来存储所有矩形的信息，每个矩形包括操作类型（d 或 e）和坐标。
   • 维护一个 x 坐标的列表，用于记录所有矩形的左右边界，并进行排序，以便在扫描过程中逐一处理。

2. 操作处理：

   • 对于每个操作，根据操作类型判断是绘制还是擦除。
     • 绘制操作（d）：将新矩形的上下边界信息记录下来，更新绘制的线段。
     • 擦除操作（e）：计算当前已绘制矩形与擦除矩形的差集，移除重叠的部分。

3. 面积计算：

   • 使用相邻的 x 坐标来计算矩形的宽度，并在该宽度内累加高度（通过有效的绘制线段计算）。
   • 利用辅助函数来处理线段的并集和差集，避免重叠部分的重复计算。

关键函数分析

1. getDiff 函数：

   • 该函数用于计算绘制线段与擦除线段的差集，返回剩余的有效线段。通过对比坐标的关系，判断线段的覆盖情况，并构造新的线段列表。

2. getUnionLen 函数：

   • 该函数负责计算一组线段的有效高度，即处理重叠部分并只计算一次的总长度。通过先对线段进行排序，利用贪心策略合并重叠线段，逐步累加有效的长度。

3. 主逻辑：

   • 遍历所有的 x 坐标，分别处理相邻 x 之间的绘制和擦除操作，计算出在这些范围内的有效高度，并累加到总面积中。

cpp

#include <bits/stdc++.h>
using namespace std;

// 区间差集
vector<vector<int>> getDiff(vector<vector<int>> &draw_lines, vector<int> &erase_line) {
    vector<vector<int>> lines;
    int s1 = erase_line[0], e1 = erase_line[1];

    for (vector<int> &draw_line : draw_lines) {
        int s = draw_line[0], e = draw_line[1];

        if (s1 >= e || s >= e1) {
            lines.emplace_back(vector<int>{s, e});
        } else if (s < s1 && e1 < e) {
            lines.emplace_back(vector<int>{s, s1});
            lines.emplace_back(vector<int>{e1, e});
        } else if (s <= s1 && e <= e1) {
            lines.emplace_back(vector<int>{s, s1});
        } else if (s1 <= s && e1 <= e) {
            lines.emplace_back(vector<int>{e1, e});
        }
    }

    return lines;
}

// 区间并集长度
int getUnionLen(vector<vector<int>> &lines) {
    sort(lines.begin(), lines.end(), [](vector<int> &lineA, vector<int> &lineB) {
        if (lineA[0] != lineB[0]) {
            return lineA[0] < lineB[0];
        } else {
            return lineA[1] > lineB[1];
        }
    });

    int height = 0;
    int last_end = INT_MIN;
    for (vector<int> &line : lines) {
        int start = line[0];
        int end = line[1];

        if (last_end < end) {
            height += end - max(start, last_end);
            last_end = end;
        }
    }

    return height;
}

int solution(vector<vector<int>> &rects) {
    vector<int> listX;

    for (vector<int> &rect : rects) {
        listX.emplace_back(rect[1]); // 矩形左边边x坐标
        listX.emplace_back(rect[3]); // 矩形右边边x坐标
    }

    sort(listX.begin(), listX.end());
    int ans = 0;

    for (int i = 1; i < listX.size(); i++) {
        int preX = listX[i - 1];
        int curX = listX[i];
        int width = curX - preX;

        if (width == 0) continue;

        vector<vector<int>> draw_lines;
        for (vector<int> &rect : rects) {
            char op = rect[0];
            int x1 = rect[1], y1 = rect[2], x2 = rect[3], y2 = rect[4];

            if (x1 <= preX && curX <= x2) {
                vector<int> line{y2, y1}; // 这里的y2和y1应该是相反的，y2是下边缘，y1是上边缘
                if (op == 'd') {
                    draw_lines.emplace_back(line);
                } else {
                    draw_lines = getDiff(draw_lines, line);
                }
            }
        }

        ans += width * getUnionLen(draw_lines);
    }

    return ans;
}

int main() {
    int n;
    cin >> n;

    vector<vector<int>> rects;

    for (int i = 0; i < n; i++) {
        char op;
        int x1, y1, x2, y2;
        cin >> op >> x1 >> y1 >> x2 >> y2;
        rects.emplace_back(vector<int>{op, x1, y1, x2, y2});
    }

    cout << solution(rects) << endl;

    return 0;
}

python

def get_diff(draw_lines, erase_line):
    lines = []
    s1, e1 = erase_line[0], erase_line[1]

    for draw_line in draw_lines:
        s, e = draw_line[0], draw_line[1]

        if s1 >= e or s >= e1:
            lines.append([s, e])
        elif s < s1 and e1 < e:
            lines.append([s, s1])
            lines.append([e1, e])
        elif s <= s1 and e <= e1:
            lines.append([s, s1])
        elif s1 <= s and e1 <= e:
            lines.append([e1, e])

    return lines


def get_union_len(lines):
    lines.sort(key=lambda line: (line[0], -line[1]))  # 按照起始位置升序，结束位置降序

    height = 0
    last_end = float('-inf')
    for line in lines:
        start, end = line[0], line[1]

        if last_end < end:
            height += end - max(start, last_end)
            last_end = end

    return height


def solution(rects):
    list_x = []

    for rect in rects:
        list_x.append(rect[1])  # 矩形左边边x坐标
        list_x.append(rect[3])  # 矩形右边边x坐标

    list_x = sorted(set(list_x))  # 去重并排序
    ans = 0

    for i in range(1, len(list_x)):
        pre_x = list_x[i - 1]
        cur_x = list_x[i]
        width = cur_x - pre_x

        if width == 0:
            continue

        draw_lines = []
        for rect in rects:
            op = rect[0]
            x1, y1, x2, y2 = rect[1], rect[2], rect[3], rect[4]

            if x1 <= pre_x and cur_x <= x2:
                line = [y2, y1]  # 这里的y2和y1是上下边界
                if op == 'd':
                    draw_lines.append(line)
                else:
                    draw_lines = get_diff(draw_lines, line)

        ans += width * get_union_len(draw_lines)

    return ans


if __name__ == "__main__":
    n = int(input())
    rects = []

    for _ in range(n):
        op, x1, y1, x2, y2 = input().split()
        x1, y1, x2, y2 = int(x1), int(y1), int(x2), int(y2)
        rects.append([op, x1, y1, x2, y2])

    print(solution(rects))

java

import java.util.*;

public class Main {
    
    // 区间差集
    public static List<int[]> getDiff(List<int[]> drawLines, int[] eraseLine) {
        List<int[]> lines = new ArrayList<>();
        int s1 = eraseLine[0], e1 = eraseLine[1];

        for (int[] drawLine : drawLines) {
            int s = drawLine[0], e = drawLine[1];

            if (s1 >= e || s >= e1) {
                lines.add(new int[]{s, e});
            } else if (s < s1 && e1 < e) {
                lines.add(new int[]{s, s1});
                lines.add(new int[]{e1, e});
            } else if (s <= s1 && e <= e1) {
                lines.add(new int[]{s, s1});
            } else if (s1 <= s && e1 <= e) {
                lines.add(new int[]{e1, e});
            }
        }

        return lines;
    }

    // 区间并集长度
    public static int getUnionLen(List<int[]> lines) {
        lines.sort((lineA, lineB) -> {
            if (lineA[0] != lineB[0]) {
                return Integer.compare(lineA[0], lineB[0]);
            } else {
                return Integer.compare(lineB[1], lineA[1]);
            }
        });

        int height = 0;
        int lastEnd = Integer.MIN_VALUE;
        for (int[] line : lines) {
            int start = line[0];
            int end = line[1];

            if (lastEnd < end) {
                height += end - Math.max(start, lastEnd);
                lastEnd = end;
            }
        }

        return height;
    }

    public static int solution(List<int[]> rects) {
        Set<Integer> listX = new HashSet<>();

        for (int[] rect : rects) {
            listX.add(rect[1]); // 矩形左边边x坐标
            listX.add(rect[3]); // 矩形右边边x坐标
        }

        List<Integer> sortedX = new ArrayList<>(listX);
        Collections.sort(sortedX);
        int ans = 0;

        for (int i = 1; i < sortedX.size(); i++) {
            int preX = sortedX.get(i - 1);
            int curX = sortedX.get(i);
            int width = curX - preX;

            if (width == 0) continue;

            List<int[]> drawLines = new ArrayList<>();
            for (int[] rect : rects) {
                char op = (char) rect[0];
                int x1 = rect[1], y1 = rect[2], x2 = rect[3], y2 = rect[4];

                if (x1 <= preX && curX <= x2) {
                    int[] line = {y2, y1}; // 这里的y2和y1是上下边界
                    if (op == 'd') {
                        drawLines.add(line);
                    } else {
                        drawLines = getDiff(drawLines, line);
                    }
                }
            }

            ans += width * getUnionLen(drawLines);
        }

        return ans;
    }

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt();
        List<int[]> rects = new ArrayList<>();

        for (int i = 0; i < n; i++) {
            char op = scanner.next().charAt(0);
            int x1 = scanner.nextInt();
            int y1 = scanner.nextInt();
            int x2 = scanner.nextInt();
            int y2 = scanner.nextInt();
            rects.add(new int[]{op, x1, y1, x2, y2});
        }

        System.out.println(solution(rects));
    }
}

题目内容

实现一个简单的绘图模块，绘图模块仅支持矩形的绘制和擦除

• 当新绘制的矩形与之前的图形重叠时，对图形取并集
• 当新擦除的矩形与之前的图形重叠时，对图形取差集

给定一系列矩形的绘制和擦除操作，计算最终图形的面积。

下面给出示例 $1$ 和示例 $2$ 的图示

示例 $1$ ：

两步绘制的矩形如左侧所示，取并集后得到的图形如右侧所示

示例 $2$ ：

第一步绘制的矩形在左侧用实线表示，第二步擦除的矩形在左侧用虚线表示，取差集后得到图像如右侧所示

输入描述

绘图模块采用二维坐标系，输入第一行位操作的数量 $N$ ，接下来的 $N$ 行格式为：

• $d$ $x_1$ $y_1$ $x_2$ $y_2$，$d$ 表示进行绘制操作，($x_1, y_1$)为矩形左上角坐标，($x_2, y_2$)为矩形右下角坐标
• $e$ $x_1$ $y_1$ $x_2$ $y_2$，$e$ 表示进行擦除操作，($x_1, y_1$)为矩形左上角坐标，($x_2, y_2$)为矩形右下角坐标

坐标为整数，且数据范围为 $[-100, 100]$，用例保证坐标有效

输出描述

输出最终图形的面积

样例1

输入

2
d 0 2 2 0
d -1 1 1 -1

输出

7

样例2

输入

2
d 0 2 2 0
e -1 1 1 -1

输出

3