P83412

奇偶覆盖

难度 7 级 初三 扫描线、线段树
讨论 统计 2通过 3提交 66.7%通过率 旧版界面
时间限制 1 秒 内存限制 512 MB

题目描述

在平面内有一些矩形,它们的两条边都平行于坐标轴。

我们称一个点被某个矩形覆盖,是指这个点在矩形的内部或者边界上。

请问,被奇数个矩形覆盖和被偶数 (\geq 2) 个矩形覆盖的点的面积分别是多少?

输入

输入的第一行包含一个整数 n,表示矩形的个数。

接下来 n 行描述这些矩形,其中第 i 行包含四个整数li,bi,ri,ti,
表示矩形的两个对角坐标分别为 (li,bi),(ri,ti)。

输出

输出两行。

第一行包含一个整数,表示被奇数个矩形覆盖的点的面积。

第二行包含一个整数,表示被偶数 (\geq 2) 个矩形覆盖的点的面积。

样例

样例 1
输入
3
1 1 3 3
2 2 4 4
3 3 5 5
输出
8
2

提示

对于所有评测用例, 1 \leq n \leq 10^5 , 0 <= li< ri <= 10^9 ,0 <= bi< ti<= 10^9。

蓝桥杯 2020 年国赛 A 组 I 题。

来源

蓝桥杯

Tab 缩进 · 提交后可在下方查看评测状态
请先登录后再提交