问题 D: 几何任务

https://qoj.ac/contest/1913/problem/9043?v=1 在一个二维平面上有 $ n $ 条红线和 $ n $ 条蓝线。第 $ i $ 条红线的方程为 $ y = a_i x + b_i $ , 第 $ i $ 条蓝线的方程为 $ x = c_i $ 。 定义将一条红线与一条蓝线配对的“价值”为它们交点的 $ y $ 坐标。你需要给每条红线都唯一配上一条蓝线，从而得到 $ n $ 个这样的价值。请你确定这 $ n $ 个价值的最大可能中位数。 长度为 $ n $ 的数组的中位数定义为该数组中第 $ \left\lceil \frac{n}{2} \right\rceil $ 大的元素。例如，数组 $ [3\, 4\, 2] $ 的中位数是 3，数组 $ [1\, 1\, 4\, 5\, 1\, 4] $ 的中位数是 4。

- 第一行包含测试用例数 $ T $ ( $ 1 \le T \le 10^5 $ )。 - 接下来是 $ T $ 组测试用例的描述。 对于每个测试用例： 1. 第一行包含一个整数 $ n $ ( $ 1 \le n \le 10^5 $ )。 2. 第二行包含 $ n $ 个整数 $ a_1\, a_2\, \dots\, a_n $ ( $ -10^9 \le a_i \le 10^9 $ )。 3. 第三行包含 $ n $ 个整数 $ b_1\, b_2\, \dots\, b_n $ ($ -10^{18} \le b_i \le 10^{18} $)。 4. 第四行包含 $ n $ 个整数 $ c_1\, c_2\, \dots\, c_n $ ($ -10^9 \le c_i \le 10^9 $)。 保证所有测试用例的 $ n $ 之和不超过 $ 10^5 $。

对于每个测试用例，输出一个整数，表示可达到的最大中位数。