30298번 - Good Triangle 다국어

You are given $n$ distinct points on the two dimensional plane.

We define the distance between two points $P=(x_1, y_1)$ and $Q=(x_2, y_2)$ as $d(P, Q)=|x_1-x_2|+|y_1-y_2|$.

Let's say that three distinct points $U, V, W$ form a good triangle if there exists a point $T$ such that $d(U, T)=d(V, T)=d(W, T)$. Note that $T$ does not have to be a lattice point.

Find the number of good triangles that can be formed by the given points.

The first line of input contains $N$.

The $i$-th line of the next $N$ lines contains two space-separated integers $x_i, y_i$, meaning that the coordinate of the $i$-th point is $(x_i, y_i)$.

Print one integer, the number of good triangles that can be formed by the given points.

• $3 \leq N \leq 500\,000$
• $-10^9 \leq x_i, y_i \leq 10^9$ ($1 \leq i \leq N$)
• $(x_i, y_i) \neq (x_j, y_j)$ if $i\ne j$ ($1 \leq i, j \leq N$)
• All values in the input are integers.