普及模拟赛 9 - C

题目描述

小艺是一位热爱设计的学生。一天，她在一张圆形餐桌的边缘上均匀标记了 $C$ 个点，从第 $0$ 个位置顺时针编号为 $0, 1, 2, \dots, C-1$，每个点代表一个可能的插花位置。

然后，她在其中 $n$ 个位置插上了鲜花。第 $i$ 朵花被插在位置 $p_i$，注意同一个位置可以插多朵花。

现在小艺想挑选三朵花作为桌面中央摆件的参照。她称一组三朵花 $(a,b,c)$ 构成一个完美三角形当且仅当：

• 设三朵花分别插在位置编号为 $a, b, c$ 上（满足 $1 \le a < b < c \le n$）；
• 餐桌圆心（也就是坐标原点 $(0, 0)$）严格在这三朵花构成的三角形内部；
• 注意：如果圆心刚好落在三角形的边或顶点上，不算作在三角形“内部”。

现在小艺想知道，一共可以从这些花中选出多少组完美三角形？

输入格式

第一行两个正整数 $n,C$ ，表示鲜花个数和圆周长。

接下来一行 $n$ 个整数，表示鲜花位置。

输出格式

输出一个整数 $x$ ，表示完美三角形数量。

数据范围

对于 $20\%$ 的数据：$3\le n\le 200,3\le c\le10^6$

对于另外 $20\%$ 的数据：$3\le n\le 10^6,3\le c\le6000$

对于另外 $30\%$ 的数据：$3\le n\le 10^6,3\le c\le10^6$ 且所有花的位置互不相同。

对于 $100\%$ 的数据：$3\le n\le 10^6,3\le c\le10^6$

输入输出样例

输入样例1

8 10
0 2 5 5 6 9 0 0

输出样例1

6

样例解释：

原点严格地位于顶点为 $p_1$、$p_2$ 和 $p_5$ 的三角形内，所以 $（1，2，5）$ 是一个完美三角形。其他五个完美三角形是$（2，3，6），（2，4，6），（2，5，6），（2，5，7）$ 和$（2，5，8）$。

输入/输出样例2

见下发文件，满足花的位置互不相同。

输入/输出样例3

见下发文件。