P8398 [CCC 2022 S4] Good Triplets

$\rm Andrew$ is a very curious student. One day, he drew a circle on paper with its center at $(0,0)$. Let the circumference be $C$. The coordinates of each point on the circle are:  Now $\rm Andrew$ marks $n$ points on the circle. The $i$-th point is placed at $p_i$. $\rm Andrew$ may place multiple points at the same position. A good triangle $(a,b,c)$ is defined as: - $1 \le a < b < c \le n$. - The origin $(0,0)$ lies strictly inside the triangle whose vertices are at $p_a$, $p_b$, and $p_c$. Note in particular that the origin is not on the boundary of the triangle. $\rm Andrew$ asks you how many good triangles there are.

The first line contains two integers $n, c$, representing the number of points and the circumference of the circle. The next line contains $n$ integers. Their meaning is described above.

Output an integer $x$, indicating that there are $x$ good triangles.

Explanation for Sample $1$: $\rm Andrew$ drew the following figure:  The origin lies strictly inside the triangle with vertices at $p_1$, $p_2$, and $p_5$, so $(1,2,5)$ is a good triangle. The other five good triplets are $(2,3,6)$, $(2,4,6)$, $(2,5,6)$, $(2,5,7)$, and $(2,5,8)$. For $20\%$ of the testdata: $3 \le n \le 200$, $3 \le c \le 10^6$. For another $20\%$ of the testdata: $3 \le n \le 10^6$, $3 \le c \le 6000$. For $40\%$ of the testdata: $3 \le n \le 10^6$, $3 \le c \le 10^6$, and all point positions are pairwise distinct. For $100\%$ of the testdata: $3 \le n \le 10^6$, $3 \le c \le 10^6$. Translated by ChatGPT 5