Triangles
本题没有可用的提交语言。
Description
You are given $n$ distinct lines in the plane. Each of them is either horizontal ($y=c$), vertical ($x=c$) or diagonal ($x+y=c$). You need to find the number of non-degenerate triangles such that each of their sides lies on some of the given lines. For example, there are $4$ such triangles in the following configuration:
The first line contains an integer $n$ ($1 \leq n \leq 3\,000$), the number of lines. Each of the next $n$ lines describes a single line as a character $d$ and an integer $c$ in the following way:
- $d$ is equal to "H" if the line is horizontal; $c$ is an integer such that the line is described by the equation $y=c$;
- $d$ is equal to "V" if the line is vertical; $c$ is an integer such that the line is described by the equation $x=c$;
- $d$ is equal to "D" if the line is diagonal; $c$ is an integer such that the line is described by the equation $x+y=c$;
Output a single integer, the total number of non-degenerate triangles with sides on the given lines.
Input
The first line contains an integer $n$ ($1 \leq n \leq 3\,000$), the number of lines. Each of the next $n$ lines describes a single line as a character $d$ and an integer $c$ in the following way:
- $d$ is equal to "H" if the line is horizontal; $c$ is an integer such that the line is described by the equation $y=c$;
- $d$ is equal to "V" if the line is vertical; $c$ is an integer such that the line is described by the equation $x=c$;
- $d$ is equal to "D" if the line is diagonal; $c$ is an integer such that the line is described by the equation $x+y=c$;
Output
Output a single integer, the total number of non-degenerate triangles with sides on the given lines.
5
V 0
D 1
H 0
D 4
H 2
3
V 1
H 2
D 3
4
0