← 返回题目列表

Codeforces · 1466/A

A. 牛的困境

中文机器翻译题面 查看原题

阿古斯负责守护木卫一,它不是一头普通的牛。艾欧是一位不折不扣的探险家,她经常外出,这让阿古斯的生活充满压力。于是,牛郎决定为艾欧建造一个封闭的牧场。

阿古斯照料木卫一的河边生长着 $$$n$$$ 树。对于这个问题,河流可以被视为笛卡尔坐标系的 $$$OX$$$ 轴,$$$n$$$ 树被视为 $$$y$$$ 坐标等于 $$$0$$$ 的点。还有一棵树生长在 $$$(0, 1)$$$ 点。

阿格斯将一根绳子绑在三棵树上,形成一个三角形牧场。它的确切形状对艾欧来说并不重要,但它的面积对她来说至关重要。阿古斯布置栅栏的方式可能有很多种,但艾欧只对那些导致牧场不同区域的方式感兴趣。计算她的牧场可能有不同区域的数量。请注意,牧场的面积必须非零。

输入

输入由多个测试用例组成。第一行包含一个整数 $$$t$$$ ($$$1 \leq t \leq 100$$$) — 测试用例的数量。然后是 $$$t$$$ 测试用例,每个测试用例用两行描述。

在每个测试用例的第一行有一个整数 $$$n$$$ ($$$1 \leq n \leq 50$$$) 表示沿河生长的树木数量。下一行包含 $$$n$$$ 不同的整数 $$$x_1 < x_2 < \ldots < x_{n - 1} < x_n$$$ ($$$1 \leq x_i \leq 50$$$),沿河生长的树木的 $$$x$$$ 坐标。

输出

在一行中输出一个整数,以树为顶点的三角形可能具有的不同非零区域的数量。

示例

输入 #1

8
4
1 2 4 5
3
1 3 5
3
2 6 8
2
1 2
1
50
5
3 4 5 6 8
3
1 25 26
6
1 2 4 8 16 32

输出 #1

4
2
3
1
0
5
3
15

注意

在第一个测试用例中,我们有 $$$6$$$ 非简并三角形,其面积如下:$$$0.5$$$、$$$0.5$$$、$$$1$$$、$$$1.5$$$、$$$1.5$$$ 和 $$$2$$$。牧场可以有 $$$4$$$ 不同的区域,因此 $$$4$$$ 就是答案。

在第二个测试用例中,我们有 $$$3$$$ 非退化三角形,其面积如下:$$$1$$$、$$$1$$$ 和 $$$2$$$。牧场可以有 $$$2$$$ 不同的区域,所以 $$$2$$$ 就是答案。

下面两张图展示了第二个测试用例的情况。第一张图中的蓝色三角形的面积为$$$1$$$。第二张图中的红色三角形的面积为$$$2$$$。