A15436. House Planning
编程题
普及/提高-
知识点
题目描述
There are $n$ houses in your city arranged on an axis at points $h_1, h_2, \ldots, h_n$ . You want to build a new house for yourself and consider two options where to place it: points $p_1$ and $p_2$ .
As you like visiting friends, you have calculated in advance the distances from both options to all existing houses. More formally, you have calculated two arrays $d_1$ , $d_2$ : $d_{i, j} = \left|p_i - h_j\right|$ , where $|x|$ defines the absolute value of $x$ .
After a long time of inactivity you have forgotten the locations of the houses $h$ and the options $p_1$ , $p_2$ . But your diary still keeps two arrays — $d_1$ , $d_2$ , whose authenticity you doubt. Also, the values inside each array could be shuffled, so values at the same positions of $d_1$ and $d_2$ may correspond to different houses. Pay attention, that values from one array could not get to another, in other words, all values in the array $d_1$ correspond the distances from $p_1$ to the houses, and in the array $d_2$ — from $p_2$ to the houses.
Also pay attention, that the locations of the houses $h_i$ and the considered options $p_j$ could match. For example, the next locations are correct: $h = \{1, 0, 3, 3\}$ , $p = \{1, 1\}$ , that could correspond to already shuffled $d_1 = \{0, 2, 1, 2\}$ , $d_2 = \{2, 2, 1, 0\}$ .
Check whether there are locations of houses $h$ and considered points $p_1$ , $p_2$ , for which the founded arrays of distances would be correct. If it is possible, find appropriate locations of houses and considered options.
As you like visiting friends, you have calculated in advance the distances from both options to all existing houses. More formally, you have calculated two arrays $d_1$ , $d_2$ : $d_{i, j} = \left|p_i - h_j\right|$ , where $|x|$ defines the absolute value of $x$ .
After a long time of inactivity you have forgotten the locations of the houses $h$ and the options $p_1$ , $p_2$ . But your diary still keeps two arrays — $d_1$ , $d_2$ , whose authenticity you doubt. Also, the values inside each array could be shuffled, so values at the same positions of $d_1$ and $d_2$ may correspond to different houses. Pay attention, that values from one array could not get to another, in other words, all values in the array $d_1$ correspond the distances from $p_1$ to the houses, and in the array $d_2$ — from $p_2$ to the houses.
Also pay attention, that the locations of the houses $h_i$ and the considered options $p_j$ could match. For example, the next locations are correct: $h = \{1, 0, 3, 3\}$ , $p = \{1, 1\}$ , that could correspond to already shuffled $d_1 = \{0, 2, 1, 2\}$ , $d_2 = \{2, 2, 1, 0\}$ .
Check whether there are locations of houses $h$ and considered points $p_1$ , $p_2$ , for which the founded arrays of distances would be correct. If it is possible, find appropriate locations of houses and considered options.
输入格式
The first line of the input contains a single integer $t$ ( $1 \le t \le 10^3$ ) — the number of test cases. The description of test cases follows.
The first line of each test case contains one integer $n$ ( $1 \le n \le 10^3$ ) — the length of arrays $d_1$ , $d_2$ .
The next two lines contain $n$ integers each: arrays $d_1$ and $d_2$ ( $0 \le d_{i, j} \le 10^9$ ) respectively.
It is guaranteed that the sum of $n$ over all test cases doesn't exceed $2 \cdot 10^3$ .
The first line of each test case contains one integer $n$ ( $1 \le n \le 10^3$ ) — the length of arrays $d_1$ , $d_2$ .
The next two lines contain $n$ integers each: arrays $d_1$ and $d_2$ ( $0 \le d_{i, j} \le 10^9$ ) respectively.
It is guaranteed that the sum of $n$ over all test cases doesn't exceed $2 \cdot 10^3$ .
输出格式
For each test case, output a single line "NO" if there is no answer.
Otherwise output three lines. The first line must contain "YES". In the second line, print $n$ integers $h_1, h_2, \ldots, h_n$ . In the third line print two integers $p_1$ , $p_2$ .
It must be satisfied that $0 \le h_i, p_1, p_2 \le 2 \cdot 10^9$ . We can show that if there is an answer, then there is one satisfying these constraints.
If there are several answers, output any of them.
Otherwise output three lines. The first line must contain "YES". In the second line, print $n$ integers $h_1, h_2, \ldots, h_n$ . In the third line print two integers $p_1$ , $p_2$ .
It must be satisfied that $0 \le h_i, p_1, p_2 \le 2 \cdot 10^9$ . We can show that if there is an answer, then there is one satisfying these constraints.
If there are several answers, output any of them.
输入输出样例
输入 #1
4 1 5 5 2 10 12 5 20 2 10 33 26 69 4 0 2 1 2 2 2 1 0
输出 #1
YES 5 0 10 NO YES 0 43 33 69 YES 1 0 3 3 1 1
说明/提示
In the image below you can see the sample solutions. Planned houses are shown in bright colours: pink and purple. Existing houses are dim.
In test case $1$ , the first planned house is located at point $0$ , the second at point $10$ . The existing house is located at point $5$ and is at a distance of $5$ from both planned houses.
It can be shown that there is no answer for test case $2$ .
In test case $3$ , the planned houses are located at points $33$ and $69$ .
Note that in test case $4$ , both plans are located at point $1$ , where one of the existing houses is located at the same time. It is a correct placement.
In test case $1$ , the first planned house is located at point $0$ , the second at point $10$ . The existing house is located at point $5$ and is at a distance of $5$ from both planned houses.
It can be shown that there is no answer for test case $2$ .
In test case $3$ , the planned houses are located at points $33$ and $69$ .
Note that in test case $4$ , both plans are located at point $1$ , where one of the existing houses is located at the same time. It is a correct placement.
