CF2180D.Insolvable Disks

You are given $n$ different integer points $x_1 \lt x_2 \lt \ldots \lt x_n$ on the X-axis of the plane. For each $1 \le i \le n$, you have to pick a real value $r_i \gt 0$ and draw a disk with radius $r_i$ and center $x_i$ such that no two disks overlap.

You want to choose values $r_i$ in such a way that the number of tangent pairs of disks is maximized, and you have to find this maximum value.

We say that two disks overlap if the area of their intersection is positive. In particular, two outer tangent disks do not overlap.

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

你需要选择这些 $r_i$ 的值，使得相切的圆盘对数最大化，并求出该最大值。

我们称两个圆盘重叠，当且仅当它们的交集面积为正。特别地，两个外切圆盘不视为重叠。

Each test contains multiple test cases. The first line contains the number of test cases $t$ ($1 \le t \le 10^4$). The description of the test cases follows.

The first line of each test case contains a single integer $n$ ($1 \le n \le 2\cdot10^6$) — the number of points in that test case.

The second line of each test case contains $n$ integers $x_1, x_2, \ldots x_n$ ($0 \le x_1 \lt x_2 \lt \ldots \lt x_n \le 10^9$) — the coordinates of the points in that test case.

It's also guaranteed that the sum of $n$ over all test cases is at most $2\cdot10^6$.

每个测试包含多个测试用例。第一行包含测试用例的数量 $t$（$1 \le t \le 10^4$）。随后是各测试用例的描述。

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

每个测试用例的第二行包含 $n$ 个整数 $x_1, x_2, \ldots, x_n$（$0 \le x_1 \lt x_2 \lt \ldots \lt x_n \le 10^9$）—— 表示该测试用例中各点的坐标。

此外，保证所有测试用例的 $n$ 值之和不超过 $2\cdot10^6$。

For each test case, print a single integer denoting the maximum number of tangent pairs of disks in that test case.

对于每个测试用例，输出一个整数，表示该测试用例中圆盘的相切对的最大数量。

In the first test case, you can let $r_1 = r_3 = 0.25$ and $r_2 = 0.75$ so the 1-st and 2-nd disks and the 2-nd and 3-rd disks will be pairwise tangent.

Best solution for the first test case

In the second test case, you can let $r_1 = 0.4$, $r_2 = 0.6$, $r_3 = 0.2$, and $r_4 = 0.8$ so the 1-st and 2-nd disks and 3-rd and 4-th disks will be pairwise tangent.

Best solution for the second test case

The best solution in the third test case is to set $r_i = 0.5$ for each $1 \le i \le 6$ so the 1-st and 2-nd disks, 3-rd and 4-th disks, and 5-th and 6-th disks will be pairwise tangent.

Link to the visualizer

在第一个测试用例中，你可以令 $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 个圆盘两两相切。

第二个测试用例的最优解

第三个测试用例的最优解是：对每个 $1 \le i \le 6$，均设 $r_i = 0.5$，使得第 1 个与第 2 个圆盘、第 3 个与第 4 个圆盘、以及第 5 个与第 6 个圆盘两两相切。

可视化工具链接