题目描述

Curling is a sport in which players slide stones on a sheet of ice toward a target area. The team with the nearest stone to the center of the target area wins the game.

Two teams, Red and Blue, are competing on the number axis. After the game there are $(n+m)$ stones remaining on the axis, $n$ of them for the Red team and the other $m$ of them for the Blue. The $i$-th stone of the Red team is positioned at $a_i$ and the $i$-th stone of the Blue team is positioned at $b_i$.

Let $c$ be the position of the center of the target area. From the description above we know that if there exists some $i$ such that $1 \le i \le n$ and for all $1 \le j \le m$ we have $|c - a_i| < |c - b_j|$ then Red wins the game. What's more, Red is declared to win $p$ points if the number of $i$ satisfying the constraint is exactly $p$.

Given the positions of the stones for team Red and Blue, your task is to determine the position $c$ of the center of the target area so that Red wins the game and scores as much as possible. Note that $c$ can be any real number, not necessarily an integer.

输入格式

There are multiple test cases. The first line of the input contains an integer $T$ indicating the number of test cases. For each test case:

The first line contains two integers $n$ and $m$ ($1 \le n, m \le 10^5$) indicating the number of stones for Red and the number of stones for Blue.

The second line contains $n$ integers $a_1, a_2, \cdots, a_n$ ($1 \le a_i \le 10^9$) indicating the positions of the stones for Red.

The third line contains $m$ integers $b_1, b_2, \cdots, b_m$ ($1 \le b_i \le 10^9$) indicating the positions of the stones for Blue.

It's guaranteed that neither the sum of $n$ nor the sum of $m$ will exceed $5 \times 10^5$.

输出格式

For each test case output one line. If there exists some $c$ so that Red wins and scores as much as possible, output one integer indicating the maximum possible $\textbf{score}$ of Red (NOT $c$). Otherwise output Impossible (without quotes) instead.

题目大意

[ICPC2020 Nanjing R] Let's Play Curling

题目描述

红队和蓝队在冰面上向目标区域滑动冰壶，距离目标区域中心最近的队伍获胜。

两支队伍在一条直线上竞争。比赛结束后，有 $(n+m)$ 个冰壶在直线上, $n$ 个是红队的，剩下 $m$ 个是蓝队的。 红队的第 $i$ 个冰壶被放在 $a_i$ ，蓝队的第 $i$ 个冰壶被放在 $b_i$ 。

设 $c$ 是中心。如果存在一些 $i$ 使得 $1 \le i \le n$ 并且对于所有 $1 \le j \le m$ 都有 $|c - a_i| < |c - b_j|$ 红队就赢得比赛。另外，如果满足条件的 $i$ 的数目是 $p$ ，则认为红队赢得 $p$ 分。

给你红蓝两队的冰壶的位置，请你确定中心 $c$ 的值，使红队得分最多。注意， $c$ 是任意实数，不一定是整数。

输入格式

有很多测试样例。第一行输入一个整数 $T$ ，表示样例数量。对于每个测试样列：

第一行包括两个整数 $n$ 和 $m$ ($1 \le n, m \le 10^5$) 分别表示红队和蓝队的冰壶数量。

第二行包括 $n$ 个整数 $a_1, a_2, \cdots, a_n$ ($1 \le a_i \le 10^9$) 表示红队的冰壶的位置。

第三行包括 $m$ 个整数 $b_1, b_2, \cdots, b_m$ ($1 \le b_i \le 10^9$)表示蓝队的冰壶的位置。

数据保证 $n$ 的总和以及 $m$ 的总和都不会超过 $5 \times 10^5$ 。

输出格式

每一个测试样列输出一行。如果存在 $c$ 使得红队获胜且得分最多, 输出一个整数表示红队最大 $\textbf{ 得分 }$ (不是 $c$) 。否则输出 Impossible ( 不带等号 ) 。

样例 #1

样例输入 #1

3
2 2
2 3
1 4
6 5
2 5 3 7 1 7
3 4 3 1 10
1 1
7
7

样例输出 #1

2
3
Impossible

提示

对于第一个样例，当 $c = 2.5$ 时，红队的位于 2 和 3 的冰壶可以得分。

对于第二个样例，当 $c = 7$ 时，红队的位于 5 和 7 的冰壶可以得分。

3
2 2
2 3
1 4
6 5
2 5 3 7 1 7
3 4 3 1 10
1 1
7
7

2
3
Impossible

提示

For the first sample test case we can assign $c = 2.5$ so that the stones at position 2 and 3 for Red will score.

For the second sample test case we can assign $c = 7$ so that the stones at position 5 and 7 for Red will score.