CF1781E.Rectangle Shrinking
普及/提高-
通过率:0%
AC君温馨提醒
该题目为【codeforces】题库的题目,您提交的代码将被提交至codeforces进行远程评测,并由ACGO抓取测评结果后进行展示。由于远程测评的测评机由其他平台提供,我们无法保证该服务的稳定性,若提交后无反应,请等待一段时间后再进行重试。
题目描述
Each test contains multiple test cases. The first line contains the number of test cases t ( 1≤t≤104 ). The description of the test cases follows.
The first line of each test case contains a single integer n ( 1≤n≤2⋅105 ) — the number of rectangles.
Each of the next n lines contains four integers ui,li,di,ri ( 1≤ui≤di≤2 ; 1≤li≤ri≤109 ) — 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⋅105 .
输入格式
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 ui′,li′,di′,ri′ . If you remove the i -th rectangle, print ui′=li′=di′=ri′=0 . Otherwise, these numbers denote the new coordinates of the top-left and the bottom-right corners of the i -th rectangle, satisfying ui≤ui′≤di′≤di ; li≤li′≤ri′≤ri .
If there are multiple solutions, print any.
输出格式
The picture in the statement illustrates the first test case.
输入输出样例
输入#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.