The Morning Star
Contest: Codeforces Round 886 (Div. 4)
Difficulty rating: 1500
Tags: combinatorics, data structures, geometry, implementation, math, sortings

A compass points directly toward the morning star. It can only point in one of eight directions: the four cardinal directions (N, S, E, W) or some combination (NW, NE, SW, SE). Otherwise, it will break.

The directions the compass can point.

There are $$$n$$$ distinct points with integer coordinates on a plane. How many ways can you put a compass at one point and the morning star at another so that the compass does not break?

Input format:
Each test contains multiple test cases. The first line contains the number of test cases $$$t$$$ ($$$1 \le t \le 10^4$$$). The description of the test cases follows.

The first line of each test case contains a single integer $$$n$$$ ($$$2 \leq n \leq 2 \cdot 10^5$$$) — the number of points.

Then $$$n$$$ lines follow, each line containing two integers $$$x_i$$$, $$$y_i$$$ ($$$-10^9 \leq x_i, y_i \leq 10^9$$$) — the coordinates of each point, all points have distinct coordinates.

It is guaranteed that the sum of $$$n$$$ over all test cases doesn't exceed $$$2 \cdot 10^5$$$.

Output format:
For each test case, output a single integer — the number of pairs of points that don't break the compass.

Constraints:
Time limit: 2.0 s
Memory limit: 256.0 MB

Note:
In the first test case, any pair of points won't break the compass:

- The compass is at $$$(0,0)$$$, the morning star is at $$$(-1,-1)$$$: the compass will point $$$\text{SW}$$$.
- The compass is at $$$(0,0)$$$, the morning star is at $$$(1,1)$$$: the compass will point $$$\text{NE}$$$.
- The compass is at $$$(-1,-1)$$$, the morning star is at $$$(0,0)$$$: the compass will point $$$\text{NE}$$$.
- The compass is at $$$(-1,-1)$$$, the morning star is at $$$(1,1)$$$: the compass will point $$$\text{NE}$$$.
- The compass is at $$$(1,1)$$$, the morning star is at $$$(0,0)$$$: the compass will point $$$\text{SW}$$$.
- The compass is at $$$(1,1)$$$, the morning star is at $$$(-1,-1)$$$: the compass will point $$$\text{SW}$$$.

In the second test case, only two pairs of points won't break the compass:

- The compass is at $$$(6,9)$$$, the morning star is at $$$(10,13)$$$: the compass will point $$$\text{NE}$$$.
- The compass is at $$$(10,13)$$$, the morning star is at $$$(6,9)$$$: the compass will point $$$\text{SW}$$$.

Example input:
5
3
0 0
-1 -1
1 1
4
4 5
5 7
6 9
10 13
3
-1000000000 1000000000
0 0
1000000000 -1000000000
5
0 0
2 2
-1 5
-1 10
2 11
3
0 0
-1 2
1 -2

Example output:
6
2
6
8
0

Editorial:
Let's look at four directions of the line connecting the compass and morning star: vertical, horizontal, with slope $$$1$$$ (looks like /), and with slope $$$-1$$$ (looks like \).
• vertical: the two points need to have the same $$$y$$$-coordinate. If there are $$$k$$$ points with the same $$$y$$$-coordinate, then how many pairs are possible for the morning star and compass? Well, there are $$$k$$$ possibilities for the compass, and $$$k-1$$$ for the morning star, so there are a total of $$$k(k-1)$$$ valid pairs. In this case, we can use a data structure like a C++ map to count the number of points at each $$$y$$$-coordinate, and add $$$k(k-1)$$$ to the total for each $$$k$$$ in the map.
• horizontal: the two points need to have the same $$$x$$$-coordinate. Similarly, we count pairs with the same $$$x$$$-coordinate using a map.
• slope $$$1$$$: note that all lines of this form can be written as $$$x-y=c$$$ for a constant $$$c$$$. (Draw some examples out for $$$c=-1, 0, 1$$$.) So we can use a map to count values of $$$x-y$$$, and add to the total.
• slope $$$-1$$$: similarly, all such lines can be written as $$$x+y=c$$$ for a constant $$$c$$$.