310553: CF1850G. The Morning Star
Description
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?
InputEach 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$.
OutputFor each test case, output a single integer — the number of pairs of points that don't break the compass.
ExampleInput5 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 -2Output
6 2 6 8 0Note
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}$.
Input
题意翻译
### 题意简述 本题有多组数据。 给定$n$个点，第$i$个点的坐标为$x_i$，$y_i$。 现需要将星星和指南针放在任意两个点上，使得星星在指南针的正北、正东、正西、正南、正东南、正东北、正西南或正西北方向，求一共几种放法。（如果对此不太理解结合样例解释） ### 数据范围 $2\leq n \leq 2 \cdot 10^5$ $-10^9\leq x_i,y_i \leq 10^9$ ### 输入格式 第一行输入一个$t$，$表示数据组数。 在每组数据中，输入$n$，表示点的总数。 接下来$n$行，第$i$行输入两个数$x_i,y_i$，表示第$i$个点的坐标。 ### 输出格式 输出共$t$行，每行一个整数，表示第$i$组数据的结果。 ### 说明/提示 在第一组数据中： 指南针在$(0,0)$，星星在$(-1,-1)$，在指南针的正西南方向。 指南针在$(0,0)$，星星在$(1,1)$，在指南针的正东北方向。 指南针在$(-1,-1)$，星星在$(0,0)$，在指南针的正东北方向。 指南针在$(-1,-1)$，星星在$(1,1)$，在指南针的正东北方向。 指南针在$(1,1)$，星星在$(0,0)$，在指南针的正西南方向。 指南针在$(1,1)$，星星在$(-1,-1)$，在指南针的正西南方向。 所以答案为6。 在第二组数据中： 指南针在$(6,9)$，星星在$(10,13)$，在指南针的正东北方向。 指南针在$(10,13)$，星星在$(6,9)$，在指南针的正西南方向。 所以答案是2。Output
输入数据格式：
- 第一行包含一个整数t（1≤t≤10^4），表示测试用例的数量。
- 每个测试用例的第一行包含一个整数n（2≤n≤2×10^5），表示点的数量。
- 接下来的n行，每行包含两个整数x_i, y_i（-10^9≤x_i, y_i≤10^9），表示每个点的坐标，所有点都具有不同的坐标。
- 保证所有测试用例的n之和不超过2×10^5。
输出数据格式：
- 对于每个测试用例，输出一个整数，表示不会损坏罗盘的点对数量。
示例输入输出已在题目中给出。题目大意：有一个罗盘，它只能指向八个方向之一：四个基本方向（N, S, E, W）或它们的组合（NW, NE, SW, SE）。如果有其他方向，罗盘会损坏。平面上有n个具有整数坐标的不同点。问有多少种方式可以将罗盘放在一个点上，将晨星放在另一个点上，使得罗盘不会损坏。 输入数据格式： - 第一行包含一个整数t（1≤t≤10^4），表示测试用例的数量。 - 每个测试用例的第一行包含一个整数n（2≤n≤2×10^5），表示点的数量。 - 接下来的n行，每行包含两个整数x_i, y_i（-10^9≤x_i, y_i≤10^9），表示每个点的坐标，所有点都具有不同的坐标。 - 保证所有测试用例的n之和不超过2×10^5。 输出数据格式： - 对于每个测试用例，输出一个整数，表示不会损坏罗盘的点对数量。 示例输入输出已在题目中给出。