A16805 | $Insolvable Disks$

时间限制1s

内存限制256MB

通过 / 提交0/0

题目描述

在平面 $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

C++ 编辑器

输入

输出