配点: 4 点
問題文
在二维平面上 有 N 张长方形的纸。所有的纸都排列成边平行于 x 轴或 y 轴,i 张纸的左下角坐标是 (lx_i, ly_i) ,右上角坐标是 (rx_i, ry_i) 。 k=1,2,3, \dots, N 。请计算以下值:
- 张纸正好重叠的部分,以及 k 张纸重叠的部分的面积
制約
- 1 \leq N \leq 10^5
- 0 \leq lx_i \lt rx_i \leq 1000
- 0 \leq ly_i \lt ry_i \leq 1000
- 所有输入均为整数
入力
输入是按以下格式从标准输入给出的。
N lx_1 ly_1 rx_1 ry_1 lx_2 ly_2 rx_2 ry_2 \vdots lx_N ly_N rx_N ry_N
出力
张纸正好重叠的部分,以及 k 。 A_k 。 与
A_1 A_2 \vdots A_N
入力例 1
2 1 1 3 2 2 1 4 2
出力例 1
2 1
纸张 1 多层叠加部分的面积是 2纸张 2 多层叠加部分的面积是 1 。
入力例 2
2 1 1 3 4 3 4 6 5
出力例 2
9 0
纸张之间可能不重叠。
入力例 3
20 61 98 76 100 70 99 95 100 10 64 96 91 12 37 99 66 63 93 65 95 16 18 18 67 30 47 88 56 33 6 38 8 37 19 40 68 4 56 12 84 3 16 92 78 39 24 67 96 46 1 69 57 40 34 65 65 20 38 51 92 5 32 100 73 7 33 92 55 4 46 97 85 43 18 57 87 15 29 54 74
出力例 3
1806 990 1013 1221 567 839 413 305 228 121 58 40 0 0 0 0 0 0 0 0