[CCC 2022 S4] Good Triplets

Luogu
IDLGP8398
Time1000ms
Memory128MB
DifficultyP4
2022CCC(加拿大)
$\rm Andrew$ 是十分好奇的学生,一天他在纸上画了一个圆,圆心在 $(0,0)$ 。设周长为 $C$ ,圆上每一个点的坐标为: ![](https://cdn.luogu.com.cn/upload/image_hosting/x3ltbuv3.png) 现在 $\rm Andrew$ 在圆上画了 $n$ 个点,第 $i$ 的点画在 $p_i$ 上,$\rm Andrew$ 可能在一个位置上画多个点。 现在一个好的三角形 $(a,b,c)$ 的定义为: - $1\le a<b<c\le n$ - 原点 $(0,0)$ 严格位于顶点在 $p_a$,$P_b$ 和 $p_c$ 的三角形内。特别注意的是,原点不在三角形的周长上。 $\rm Andrew$ 问你有多少个好的三角形。 ## Input 第一行两个整数 $n,c$ ,表示点的个数和圆的周长。 接下来一行,有 $n$ 个整数,具体意义见题目描述。 ## Output 输出一个整数 $x$ ,表示有 $x$ 个好的三角形。 [samples] ## Note 样例 $1$ 解释: $\rm Andrew$ 画了下面的图: ![](https://cdn.luogu.com.cn/upload/image_hosting/o1ie0ubf.png) 原点严格地位于顶点为 $p_1$、$p_2$ 和 $p_5$ 的三角形内,所以 $(1,2,5)$ 是一个好的三角形。其他五个好三联体是$(2,3,6),(2,4,6),(2,5,6),(2,5,7)$ 和$(2,5,8)$。 对于 $20\%$ 的数据:$3\le n\le 200,3\le c\le10^6$ 对于另外 $20\%$ 的数据:$3\le n\le 10^6,3\le c\le6000$ 对于 $40\%$ 的数据:$3\le n\le 10^6,3\le c\le10^6$ 且所有点的位置互不相同。 对于 $100\%$ 的数据:$3\le n\le 10^6,3\le c\le10^6$
Samples
Input #1
8 10
0 2 5 5 6 9 0 0
Output #1
6
API Response (JSON)
{
  "problem": {
    "name": "[CCC 2022 S4] Good Triplets",
    "description": {
      "content": "$\\rm Andrew$ 是十分好奇的学生,一天他在纸上画了一个圆,圆心在 $(0,0)$ 。设周长为 $C$ ,圆上每一个点的坐标为: ![](https://cdn.luogu.com.cn/upload/image_hosting/x3ltbuv3.png) 现在 $\\rm Andrew$ 在圆上画了 $n$ 个点,第 $i$ 的点画在 $p_i$ 上,$\\rm Andrew$ 可能在一",
      "description_type": "Markdown"
    },
    "platform": "Luogu",
    "limit": {
      "time_limit": 1000,
      "memory_limit": 131072
    },
    "difficulty": {
      "LuoguStyle": "P4"
    },
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "LGP8398"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "$\\rm Andrew$ 是十分好奇的学生,一天他在纸上画了一个圆,圆心在 $(0,0)$ 。设周长为 $C$ ,圆上每一个点的坐标为:\n\n![](https://cdn.luogu.com.cn/upload/image_hosting/x3ltbuv3.png)\n\n现在 $\\rm Andrew$ 在圆上画了 $n$ 个点,第 $i$ 的点画在 $p_i$ 上,$\\rm Andrew$ 可能在一...",
      "is_translate": false,
      "language": "English"
    }
  ]
}
Full JSON Raw Segments