站外题求解o(╥﹏╥)o

Kaito_Shinichi @ 2024-11-01 20:10:10

题目描述
在平面直角坐标系中，有两个矩形（保证不相交），然后给出第三个矩形，求这两个矩形没有被第三个矩形遮住的部分的面积。

输入
输入三行，每行分别表示三个矩形的左下、右上坐标。

输出
输出没有被第三个矩形遮住的部分的面积。

输入数据 1
1 2 3 5
6 0 10 4
2 1 8 3
Copy
输出数据 1
17

by Grammar__hbw @ 2024-11-01 20:14:58

@Kaito_Shinichi 数据范围？

by hyx_0704 @ 2024-11-01 20:18:07

有点困难，好像需要求个矩阵交，整整写300B 代码。

如果你不会做，不妨思考一下简化版：

在平面直角坐标系中，有 n 个矩形（可以相交），然后给出 m 个询问矩形，求每个询问矩形没有被给出的 n 个矩形遮住的部分的面积。n,m \le 10^6。

by Grammar__hbw @ 2024-11-01 20:19:00

@hyx_0704 离线+扫描线？

by hyx_0704 @ 2024-11-01 20:19:47

矩阵交就是，两个维度上都区间交，区间交就是，[max(l_1,l_2),min(r_1,r_2)]