aproapecoliniare

Cerința

Conform unor texte antice (din noiembrie 2022), punctele $A$, $B$ și $C$ se numesc aproape coliniare dacă $d(A,B)+d(B,C)=d(A,C)$, unde $d(M,N)=|X_M-X_N|+|Y_M-Y_N|$ reprezintă distanța Manhattan dintre punctele $M$ și $N$.

Se dau coordonatele a $n$ puncte în plan $P_1,P_2,\ldots,P_n$. Găsiți numărul de triplete $(i,j,k)$ ($1 \le i,j,k \le n$, $i \neq j \neq k \neq i$) cu proprietatea că punctele $P_i$, $P_j$ și $P_k$ sunt aproape coliniare.

Date de intrare

Pe prima linie a fișierului de intrare aproapecoliniare.in se va afla numărul de puncte $n$ ($3 \le n \le 3 \cdot 10^5$).

Pe fiecare din următoarele $n$ linii se vor afla două numere $x_i$ și $y_i$ ($1 \le x_i,y_i \le 10^9$) — coordonatele punctului $P_i$.

Se garantează că toate punctele din fișierul de intrare sunt distincte.

Date de ieșire

Fișierul de ieșire aproapecoliniare.out va conține numărul de triplete $(i,j,k)$ ($1 \le i,j,k \le n$, $i \neq j \neq k \neq i$) cu proprietatea că punctele $P_i$, $P_j$ și $P_k$ sunt aproape coliniare.

Restricții

• Pentru $8$ puncte, $n \le 300$
• Pentru $12$ puncte, $n,x_i,y_i \le 800$
• Pentru $10$ puncte, $n,x_i,y_i \le 3000$
• Pentru $5$ puncte, $n \le 3000$
• Pentru $20$ de puncte, $n,x_i,y_i \le 50000$
• Pentru $10$ puncte, $n \le 50000$
• Pentru $20$ de puncte, toate coordonatele $x$ și toate coordonatele $y$ sunt distincte.
• Pentru $15$ puncte, nu se impun restricții suplimentare.

Exemple

Exemplu 1:

aproapecoliniare.in

5
1 1
2 2
3 1
3 2
3 3

aproapecoliniare.out

16

Explicații

Cele $16$ triplete din exemplu sunt:

• $(1,2,4)$ și $(4,2,1)$
• $(1,2,5)$ și $(5,2,1)$
• $(3,4,5)$ și $(5,4,3)$
• $(2,4,3)$ și $(3,4,2)$
• $(2,4,5)$ și $(5,4,2)$
• $(1,3,4)$ și $(4,3,1)$
• $(1,3,5)$ și $(5,3,1)$
• $(1,4,5)$ și $(5,4,1)$