Two parallel roads separated by a river are connected from cities A and B to an outer ring road. To ease traffic, a bridge over the river is planned. The bridge should be constructed based on the median of combined strong ground positions from both roads.
Given the number of strong positions on roads A and B (N1 and N2 respectively), and the strong ground positions on each road, calculate the midpoint (median) of the combined strong positions of both roads.
NOTE: When the strong positions are combined, repeated positions on different roads are dropped.
Example 1:
Input:
N1 = 3, N2 = 3
a[] = {3, 5, 2}
b[] = {1, 2, 3}
Output: 2.50
Explanation:
Combined unique sorted positions: {1, 2, 3, 5}
Middle points: 2 and 3
Median = (2 + 3) / 2 = 2.50
Example 2:
Input:
N1 = 2, N2 = 3
a[] = {2, 3}
b[] = {5, 6, 4}
Output: 4.00
Explanation:
Combined unique sorted positions: {2, 3, 4, 5, 6}
Middle point: 4
Median = 4.00