codeforces-scrape

Codeforces scraped problems and editorials
git clone git://git.laack.co/codeforces-scrape.git
Log | Files | Refs | README

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 ```