Rectangle Shrinking

题目描述

You have a rectangular grid of height $ 2 $ and width $ 10^9 $ consisting of unit cells. There are $ n $ rectangles placed on this grid, and the borders of these rectangles pass along cell borders. The $ i $ -th rectangle covers all cells in rows from $ u_i $ to $ d_i $ inclusive and columns from $ l_i $ to $ r_i $ inclusive ( $ 1 \le u_i \le d_i \le 2 $ ; $ 1 \le l_i \le r_i \le 10^9 $ ). The initial rectangles can intersect, be nested, and coincide arbitrarily. You should either remove each rectangle, or replace it with any of its non-empty subrectangles. In the latter case, the new subrectangle must lie inside the initial rectangle, and its borders must still pass along cell borders. In particular, it is allowed for the subrectangle to be equal to the initial rectangle. After that replacement, no two (non-removed) rectangles are allowed to have common cells, and the total area covered with the new rectangles must be as large as possible.  Illustration for the first test case. The initial rectangles are given at the top, the new rectangles are given at the bottom. Rectangle number $ 4 $ is removed.

输入输出格式

输入格式

Each test contains multiple test cases. The first line contains the number of test cases $ t $ ( $ 1 \le t \le 10^4 $ ). The description of the test cases follows. The first line of each test case contains a single integer $ n $ ( $ 1 \le n \le 2 \cdot 10^5 $ ) — the number of rectangles. Each of the next $ n $ lines contains four integers $ 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 $ ) — the coordinates of cells located in the top-left and the bottom-right corners of the rectangle, respectively. It is guaranteed that the sum of $ n $ over all test cases does not exceed $ 2 \cdot 10^5 $ .

输出格式

For each test case, first print an integer $ s $ — the largest possible covered by new rectangles area. Then print $ n $ lines with your solution to cover this area. In the $ i $ -th of these lines print four integers $ u'_i, l'_i, d'_i, r'_i $ . If you remove the $ i $ -th rectangle, print $ u'_i = l'_i = d'_i = r'_i = 0 $ . Otherwise, these numbers denote the new coordinates of the top-left and the bottom-right corners of the $ i $ -th rectangle, satisfying $ u_i \le u'_i \le d'_i \le d_i $ ; $ l_i \le l'_i \le r'_i \le r_i $ . If there are multiple solutions, print any.

输入输出样例

输入样例 #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

说明

The picture in the statement illustrates the first test case.

题目大意：有一个高为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$）。初始矩形可以相交、嵌套，或者任意重合。

你可以移除每个矩形，或者将其替换为它的任意非空子矩形。在后一种情况下，新的子矩形必须位于初始矩形内部，其边界仍然沿着单元格边界。特别是，子矩形可以与初始矩形相等。

替换之后，不允许有任何两个（未移除的）矩形有公共单元格，并且新矩形的总面积必须尽可能大。

输入输出数据格式：

输入格式：
- 每个测试包含多个测试用例。第一行包含测试用例数$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$。
- 如果有多个解决方案，可以打印任意一个。题目大意：有一个高为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$）。初始矩形可以相交、嵌套，或者任意重合。 你可以移除每个矩形，或者将其替换为它的任意非空子矩形。在后一种情况下，新的子矩形必须位于初始矩形内部，其边界仍然沿着单元格边界。特别是，子矩形可以与初始矩形相等。 替换之后，不允许有任何两个（未移除的）矩形有公共单元格，并且新矩形的总面积必须尽可能大。 输入输出数据格式： 输入格式： - 每个测试包含多个测试用例。第一行包含测试用例数$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$。 - 如果有多个解决方案，可以打印任意一个。