|시간 제한||메모리 제한||제출||정답||맞은 사람||정답 비율|
|3 초||128 MB||461||66||46||13.939%|
A river runs from north to south in a city. Houses are located along each side of the river as illustrated in Figure 1. The city plans to construct a horizontal bridge across the river so that people in both sides can reach quickly each other through the bridge.
Precisely, the left side of the river is the vertical line with the x-coordinate of -1, and the right side of the river is the vertical line with the x-coordinate of +1. The vertical strip between two sides represents the river. The bridge is represented as a horizontal segment which connects two points on both sides. The positions of the houses are given on the vertical lines.
To determine the optimal location of the bridge, the city want to minimize the sum of the distances between pairs (a, b) of houses where a is in the left side and b is in the right side. The distance between a and b is the sum of the distance from a to the end of the bridge, the length of the bridge, and the distance from the endo f the bridge to b. Thus we want to construct the bridge so that the sum of all the distances between houses in both sides is minimized.
More formally, let ai and bj be the positions of houses in the left and the right side, respectively, i = 1, ..., n and j = 1, ..., m and let h be the position of the bridge. Then the goal is to minimize the following quantity:
Σi,jd(ai, bj) = Σ∀i,j(|ai-h| + 2 + |h-bj|).
the positions of houses are given as integers on the vertical lines with the x-coorinates of -1 or +1. you should find the position of the bridge, that is, the y-coordinate of the horizontal segment representing the bridge, minimizing the sum of all the distances between the houses in both sides.
Your program is to read from standard input. The input consists of T test cases. The number of test cases T is given in the first line of the input. Each test case starts with integer n and m, the number of houses of the left and the right side, respectively, where 1 ≤ n, m ≤ 1,000,000. Each of the following n lines contains an integer a, representing the y-coordinate of a house in the left side. Also each of the following m lines contains an integer b, representing the y-coordinate of a house in the right side. Note that all the y-coordinates of the houses on each side are distinct, and -10,000,000 ≤ a, b ≤ 10,000,000.
Your program is to write to standard output. Print exactly one line for each test case. The line should contain a real value, the position of the bridge, that is, the y-coordinate of the horizontal segment minimizing the sum of all the distances between the houses of both sides; your output must contain the first digit after the decimal point, that is, simply ignore the ones from the 2nd digit after the decimal point. If there are multiple solutions, then print the smallest value of them.
2 3 4 30 -16 5 -5 25 -20 -10 4 7 18 -15 -3 2 8 20 12 -3 18 9 4