← 返回题目列表

Codeforces · 1781/E

E. 矩形缩小

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

您有一个由单元格组成的矩形网格,高度为 $$$2$$$,宽度为 $$$10^9$$$。该网格上放置了 $$$n$$$ 个矩形,这些矩形的边框沿着单元格边框。第 $$$i$$$ 矩形覆盖了从 $$$u_i$$$ 到 $$$d_i$$$ 的行和从 $$$l_i$$$ 到 $$$r_i$$$ 的列中的所有单元格($$$1 \le u_i \le d_i \le 2$$$; $$$1 \le l_i \le r_i \le 10^9$$$)。初始矩形可以任意相交、嵌套和重合。

您应该删除每个矩形,或将其替换为其任何非空子矩形。在后一种情况下,新的子矩形必须位于初始矩形内部,并且其边界仍然必须沿着单元格边界。特别地,允许子矩形等于初始矩形。

替换后,不允许两个(未删除的)矩形有公共单元,并且新矩形覆盖的总面积必须尽可能大。

第一个测试用例的插图。初始矩形在顶部给出,新矩形在底部给出。矩形数字 $$$4$$$ 被删除。

输入

每个测试包含多个测试用例。第一行包含测试用例的数量 $$$t$$$ ($$$1 \le t \le 10^4$$$)。测试用例的描述如下。

每个测试用例的第一行包含一个整数 $$$n$$$ ($$$1 \le n \le 2 \cdot 10^5$$$) - 矩形的数量。

接下来的 $$$n$$$ 行包含四个整数 $$$u_i, l_i, d_i, r_i$$$ ($$$1 \le u_i \le d_i \le 2$$$; $$$1 \le l_i \le r_i \le 10^9$$$) — 位于左上角和右下角的单元格的坐标分别是矩形的角。

保证所有测试用例的 $$$n$$$ 总和不超过 $$$2 \cdot 10^5$$$。

输出

对于每个测试用例,首先打印一个整数 $$$s$$$ — 新矩形区域覆盖的最大可能值。然后用您的解决方案打印 $$$n$$$ 行以覆盖该区域。

在这些行的第 $$$i$$$ 中打印四个整数 $$$u'_i、l'_i、d'_i、r'_i$$$。如果删除第 $$$i$$$ 个矩形,则打印 $$$u'_i = l'_i = d'_i = r'_i = 0$$$。否则,这些数字表示第 $$$i$$$ 矩形的左上角和右下角的新坐标,满足 $$$u_i \le u'_i \le d'_i \le d_i$$$; $$$l_i \le l'_i \le r'_i \le r_i$$$。

如果有多个解决方案,请打印其中一个。

示例

输入 #1

8
5
1 2 2 4
2 4 2 8
1 4 2 7
1 2 1 2
1 9 1 10
2
1 1 1 10
1 5 1 15
2
1 1 1 10
1 1 1 10
5
1 3 1 7
1 3 1 8
1 1 1 4
1 2 1 7
1 10 1 11
2
1 1 2 10
1 5 1 8
2
1 5 2 10
1 2 1 7
2
1 5 2 10
2 2 2 15
5
2 6 2 7
1 4 2 5
1 5 1 9
1 7 2 10
1 2 1 6

输出 #1

15
1 2 2 4
2 5 2 8
1 5 1 7
0 0 0 0
1 9 1 10
15
1 1 1 10
1 11 1 15
10
1 1 1 10
0 0 0 0
10
0 0 0 0
1 8 1 8
1 1 1 4
1 5 1 7
1 10 1 11
20
1 1 2 10
0 0 0 0
15
1 5 2 10
1 2 1 4
20
1 5 1 10
2 2 2 15
16
2 6 2 6
2 4 2 5
0 0 0 0
1 7 2 10
1 2 1 6

注意

声明中的图片说明了第一个测试用例。