#P3224. 矩形绘制(200分)
-
1000ms
Tried: 69
Accepted: 22
Difficulty: 8
所属公司 :
华为od
矩形绘制(200分)
题目描述
实现一个简单的绘图模块,支持在二维坐标系中绘制和擦除矩形。对于给定的一系列操作,要求计算最终图形的面积。绘制操作(d)将新矩形添加到当前图形中并与已存在的矩形进行合并,而擦除操作(e)则会从当前图形中移除与指定矩形重叠的部分。求最终面积
思路分析
为了解决这个问题,我们采用扫描线算法和区间处理的思路。具体步骤如下:
-
数据结构设计:
- 使用一个列表来存储所有矩形的信息,每个矩形包括操作类型(
d或e)和坐标。 - 维护一个 x 坐标的列表,用于记录所有矩形的左右边界,并进行排序,以便在扫描过程中逐一处理。
- 使用一个列表来存储所有矩形的信息,每个矩形包括操作类型(
-
操作处理:
- 对于每个操作,根据操作类型判断是绘制还是擦除。
- 绘制操作(
d):将新矩形的上下边界信息记录下来,更新绘制的线段。 - 擦除操作(
e):计算当前已绘制矩形与擦除矩形的差集,移除重叠的部分。
- 绘制操作(
- 对于每个操作,根据操作类型判断是绘制还是擦除。
-
面积计算:
- 使用相邻的 x 坐标来计算矩形的宽度,并在该宽度内累加高度(通过有效的绘制线段计算)。
- 利用辅助函数来处理线段的并集和差集,避免重叠部分的重复计算。
关键函数分析
-
getDiff函数:- 该函数用于计算绘制线段与擦除线段的差集,返回剩余的有效线段。通过对比坐标的关系,判断线段的覆盖情况,并构造新的线段列表。
-
getUnionLen函数:- 该函数负责计算一组线段的有效高度,即处理重叠部分并只计算一次的总长度。通过先对线段进行排序,利用贪心策略合并重叠线段,逐步累加有效的长度。
-
主逻辑:
- 遍历所有的 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 x1 y1 x2 y2,d 表示进行绘制操作,(x1,y1)为矩形左上角坐标,(x2,y2)为矩形右下角坐标
- e x1 y1 x2 y2,e 表示进行擦除操作,(x1,y1)为矩形左上角坐标,(x2,y2)为矩形右下角坐标
坐标为整数,且数据范围为 [−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