← 返回题目列表

AtCoder · typical90_ab

028. 杂乱的纸张(★4)

中文机器翻译题面 查看原题

配点: 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