2038C.md (1703B)
1 Source: https://codeforces.com/problemset/problem/2038/C 2 3 C. DIY 4 5 time limit per test 6 7 2 seconds 8 9 memory limit per test 10 11 512 megabytes 12 13 input 14 15 standard input 16 17 output 18 19 standard output 20 21 You are given a list of $n$ integers $a_1, a_2, \dots, a_n$. You need to pick $8$ elements from the list and use them as coordinates of four points. These four points should be corners of a rectangle which has its sides parallel to the coordinate axes. Your task is to pick coordinates in such a way that the resulting rectangle has the maximum possible area. The rectangle can be degenerate, i. e. its area can be $0$. Each integer can be used as many times as it occurs in the list (or less). 22 23 Input 24 25 The first line contains one integer $t$ ($1 \le t \le 25\,000$) — the number of test cases. 26 27 The first line of each test case contains one integer $n$ ($8 \le n \le 2 \cdot 10^5$). 28 29 The second line of each test case contains $n$ integers $a_1, a_2, \dots, a_n$ ($-10^9 \le a_i \le 10^9$). 30 31 Additional constraint on the input: the sum of $n$ over all test cases does not exceed $2 \cdot 10^5$. 32 33 Output 34 35 For each test case, print the answer as follows: 36 37 * if it is impossible to construct a rectangle which meets the constraints from the statement, print a single line containing the word NO (case-insensitive); 38 * otherwise, in the first line, print YES (case-insensitive). In the second line, print $8$ integers $x_1, y_1, x_2, y_2, x_3, y_3, x_4, y_4$ — the coordinates of the corners of the rectangle. You can print the corners in any order. 39 40 Example 41 42 Input 43 44 ``` 45 3 46 47 16 48 49 -5 1 1 2 2 3 3 4 4 5 5 6 6 7 7 10 50 51 8 52 53 0 0 -1 2 2 1 1 3 54 55 8 56 57 0 0 0 0 0 5 0 5 58 ``` 59 60 Output 61 62 ``` 63 YES 64 1 2 1 7 6 2 6 7 65 NO 66 YES 67 0 0 0 5 0 0 0 5 68 ```