time limit per test
2 seconds
memory limit per test
256 megabytes
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 nn 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
Each test contains multiple test cases. The first line contains the number of test cases tt (1≤t≤1041≤t≤104). The description of the test cases follows.
The first line of each test case contains a single integer nn (2≤n≤2⋅1052≤n≤2⋅105) — the number of points.
Then nn lines follow, each line containing two integers xixi, yiyi (−109≤xi,yi≤109−109≤xi,yi≤109) — the coordinates of each point, all points have distinct coordinates.
It is guaranteed that the sum of nn over all test cases doesn't exceed 2⋅1052⋅105.
Output
For each test case, output a single integer — the number of pairs of points that don't break the compass.
Example
Input
Copy
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
Output
Copy
6 2 6 8 0
Note
In the first test case, any pair of points won't break the compass:
- The compass is at (0,0)(0,0), the morning star is at (−1,−1)(−1,−1): the compass will point SWSW.
- The compass is at (0,0)(0,0), the morning star is at (1,1)(1,1): the compass will point NENE.
- The compass is at (−1,−1)(−1,−1), the morning star is at (0,0)(0,0): the compass will point NENE.
- The compass is at (−1,−1)(−1,−1), the morning star is at (1,1)(1,1): the compass will point NENE.
- The compass is at (1,1)(1,1), the morning star is at (0,0)(0,0): the compass will point SWSW.
- The compass is at (1,1)(1,1), the morning star is at (−1,−1)(−1,−1): the compass will point SWSW.
In the second test case, only two pairs of points won't break the compass:
- The compass is at (6,9)(6,9), the morning star is at (10,13)(10,13): the compass will point NENE.
- The compass is at (10,13)(10,13), the morning star is at (6,9)(6,9): the compass will point SWSW.
每个测试的时间限制 2 秒
每个测试的内存限制 256 兆字节
指南针直接指向晨星。它只能指向八个方向之一：四个基本方向（N、S、E、W）或某种组合（NW、NE、SW、SE）。否则，它会损坏。
指南针可以指向的方向。
平面上有 n
个具有整数坐标的不同点。有多少种方法可以将指南针放在一个点，将晨星放在另一个点，这样指南针就不会损坏？
输入
每个测试包含多个测试用例。第一行包含测试用例数 t
（1≤t≤104
）。测试用例的描述如下。
每个测试用例的第一行包含一个整数 n
（2≤n≤2⋅105
）— 点数。
接下来是 n
行，每行包含两个整数 xi
, yi
(−109≤xi,yi≤109
) — 每个点的坐标，所有点都有不同的坐标。
保证所有测试用例的 n
之和不超过 2⋅105
。
输出
对于每个测试用例，输出一个整数 — 不偏离指南针的点对的数量。
示例
输入副本
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
输出副本
6
2
6
8
0
注意
在第一个测试用例中，任何一对点都不会破坏指南针：
指南针位于 (0,0)
，晨星位于 (-1,-1)
：指南针将指向 SW
。
指南针位于 (0,0)
，晨星位于 (1,1)
：指南针将指向 NE
。
罗盘位于 (−1,−1)
，晨星位于 (0,0)
：罗盘将指向东北
。
罗盘位于 (−1,−1)
，晨星位于 (1,1)
：罗盘将指向东北
。
罗盘位于 (1,1)
，晨星位于 (0,0)
：罗盘将指向西南
。
罗盘位于 (1,1)
，晨星位于 (−1,−1)
：罗盘将指向西南
。
在第二个测试案例中，只有两对点不会破坏罗盘：
罗盘位于 (6,9)
，晨星位于 (10,13)
：罗盘将指向东北
。
罗盘位于 (10,13)
，晨星位于 (6,9)
：罗盘将指向西南
。
代码：
#include <iostream>
#include <vector>
#include <map>
using namespace std;
#define ll long long
ll A2(ll m) {
return m * (m - 1);
}
int main() {
int t;
cin >> t;
while (t--) {
int n;
cin >> n;
vector<pair<ll, ll>> points(n);
map<ll, ll> x_count, y_count, x_add_y_count, x_sub_y_count;
for (int i = 0; i < n; i++) {
cin >> points[i].first >> points[i].second;
x_count[points[i].first]++;
y_count[points[i].second]++;
x_add_y_count[points[i].first + points[i].second]++;
x_sub_y_count[points[i].first - points[i].second]++;
}
ll ans = 0;
for (auto& kv : x_count) {
ans += A2(kv.second);
}
for (auto& kv : y_count) {
ans += A2(kv.second);
}
for (auto& kv : x_add_y_count) {
ans += A2(kv.second);
}
for (auto& kv : x_sub_y_count) {
ans += A2(kv.second);
}
cout << ans << endl;
}
return 0;
}