#P8398. [CCC2022 S4] Good Triplets

[CCC2022 S4] Good Triplets

题目描述

Andrew\rm Andrew 是十分好奇的学生,一天他在纸上画了一个圆,圆心在 (0,0)(0,0) 。设周长为 CC ,圆上每一个点的坐标为:

现在 Andrew\rm Andrew 在圆上画了 nn 个点,第 ii 的点画在 pip_i 上,Andrew\rm Andrew 可能在一个位置上画多个点。

现在一个好的三角形 a,b,c)(a,b,c) 的定义为:

  • 1a<b<cn1\le a<b<c\le n
  • 原点 00(0,0) 严格位于顶点在 pap_aPbP_bpcp_c 的三角形内。特别注意的是,原点不在三角形的周长上。

Andrew\rm Andrew 问你有多少个好的三角形。

输入格式

第一行两个整数 n,cn,c ,表示点的个数和圆的周长。

接下来一行,有 nn 个整数,具体意义见题目描述。

输出格式

输出一个整数 xx ,表示有 xx 个好的三角形。

8 10
0 2 5 5 6 9 0 0
6

提示

样例 11 解释:

Andrew\rm Andrew 画了下面的图:

原点严格地位于顶点为 p1p_1p2p_2p5p_5 的三角形内,所以 125(1,2,5) 是一个好的三角形。其他五个好三联体是236),(246),(256),(257(2,3,6),(2,4,6),(2,5,6),(2,5,7)258(2,5,8)

对于 20%20\% 的数据:3n200,3c1063\le n\le 200,3\le c\le10^6

对于另外 20%20\% 的数据:3n106,3c60003\le n\le 10^6,3\le c\le6000

对于 40%40\% 的数据:3n106,3c1063\le n\le 10^6,3\le c\le10^6 且所有点的位置互不相同。

对于 100%100\% 的数据:3n106,3c1063\le n\le 10^6,3\le c\le10^6