AHUCM Online Judge 首页 题库 比赛 评测 排名 帮助
登录 注册

1319: 画家算法

内存限制：128 MB 时间限制：1.000 S 标准输入输出
题目类型：传统 评测方式：文本比较 上传者：
提交：10 通过：4 通过率：40%
提交提交记录统计

题目描述

画家算法也叫作优先填充，它是三维计算机图形学中处理可见性问题的一种解决方法。当将三维场景投影到二维平面的时候，需要确定哪些多边形是可见的，哪些是不可见的。（摘自 Wikipedia-画家算法）
简而言之，在图形学的渲染中，更表层的物体应该覆盖更深层的物体。这就像画画一样，一个位置可能要上好多次色，新上的颜料会将原来下面的颜料覆盖。
现在，我会给你一个画布，方便起见，我们将整个画布变成 LCD 显示屏，即将画布看作是由屏幕的一个个像素点组成的。这个画布宽 W 高 H，将这些像素按离散的整数坐标标记，即 x 轴的取值范围为 [0, W - 1]，y 轴的取值范围为 [0, H - 1]。取画布最左上角为原点，向右为 x 正方向，向下为 y 正方向。
然后我将给你 N 个矩形的左上角和右下角的坐标，表示对这个矩形内使用颜料填充，并且每次一个像素的填充需要使用一个单位的颜料。比如，对于矩形 [0, 0]~[2, 2]，填充这个矩形需要使用 9 个单位的颜料。
接着你给一个正整数 Q，表示接下来的查询次数。接下来的 Q 行，每一行再给一个矩形区域（同样使用左上和右下坐标表示），你需要回答，在这个矩形区域内曾消耗的颜料总量（包括被覆盖的）。

输入格式

第一行给出 W、H、N。
接下来 N 行以 x1 y1 x2 y2 的形式，给出需要填充的矩形区域的左上角和右下角坐标。
接下来一行给出 Q。
最后 Q 行以 x1 y1 x2 y2 的形式，给出需要查询的矩形区域的左上角和右下角坐标。

输出格式

对于 Q 次查询，给出对应的答案。

输入样例 复制 

4 4 2
0 0 2 2
1 1 3 3
3
0 0 3 3
0 1 2 3
1 0 3 2

输出样例 复制 

18
12
12

数据范围与提示

数据范围：
0 < W, H <= 105, W * H <= 105, 0 <= Q <= 105

分类标签