CFCF2180D.Insolvable Disks

普及+/提高

通过率：0%

AC君温馨提醒

该题目为【codeforces】题库的题目，您提交的代码将被提交至codeforces进行远程评测，并由ACGO抓取测评结果后进行展示。由于远程测评的测评机由其他平台提供，我们无法保证该服务的稳定性，若提交后无反应，请等待一段时间后再进行重试。

在平面 $X$ 轴上给定 $n$ 个不同的整点 $x_1 < x_2 < \ldots < x_n$ 。对于每个 $1 \leq i \leq n$ ，你需要选择一个实数 $r_i > 0$ ，并以 $x_i$ 为圆心、 $r_i$ 为半径画一个圆盘，使得任意两个圆盘都不重叠。

你希望选择 $r_i$ 的方式，使得圆盘之间互相外切的对数最大，并求出这个最大值。

我们认为，如果两个圆盘的交集面积为正，则它们重叠。特别地，如果两个圆盘恰好外切，则它们不重叠。

每组测试包含若干测试用例。第一行包含一个整数 $t$ （ $1 \leq t \leq 10^4$ ），表示测试用例的数量。

每个测试用例的第一行包含一个整数 $n$ （ $1 \leq n \leq 2\cdot 10^6$ ）——该测试用例中点的数量。

每个测试用例的第二行包含 $n$ 个整数 $x_1, x_2, \ldots, x_n$ （ $0 \leq x_1 < x_2 < \ldots < x_n \leq 10^9$ ），表示这些点的坐标。

保证所有测试用例中 $n$ 的总和不超过 $2\cdot 10^6$ 。

对于每组测试用例，输出一个整数，表示该测试用例中最多能得到多少对外切的圆盘。

输入#1

4
3
1 2 3
4
1 2 4 5
6
1 2 11 12 21 22
7
0 1 2 3 5 8 13

输出#1

在第一个测试用例中，可以取 $r_1 = r_3 = 0.25$ ， $r_2 = 0.75$ ，则第 $1$ 、 $2$ 个圆盘以及第 $2$ 、 $3$ 个圆盘两两外切。

在第二个测试用例中，可以取 $r_1 = 0.4$ ， $r_2 = 0.6$ ， $r_3 = 0.2$ ， $r_4 = 0.8$ ，则第 $1$ 、 $2$ 个圆盘以及第 $3$ 、 $4$ 个圆盘两两外切。

在第三个测试用例中，最优解是让每个 $r_i = 0.5$ ，第 $1$ 和 $2$ ， $3$ 和 $4$ ， $5$ 和 $6$ 组成为外切圆盘对。