【算法入门教育赛2】C.曼哈顿种类 C++题解与代码
比赛地址：https://www.starrycoding.com/contest/6
题目描述
牢 e e e知道在武汉有 n n n家自助店，第 i i i个自助店用坐标 ( x i , y i ) (x_i, y_i) (xi,yi)表示，因为武汉的街道都是互相垂直的，现在他想知道所有自助店之间的曼哈顿距离有多少种？
曼哈顿距离： ( x 1 , y 1 ) (x_1, y_1) (x1,y1)与 ( x 2 , y 2 ) (x_2, y_2) (x2,y2)的曼哈顿距离为： ∣ x 1 − x 2 ∣ + ∣ y 1 − y 2 ∣ |x_1 - x_2| + |y_1 - y_2| ∣x1−x2∣+∣y1−y2∣。
注意：可能有多个自助点在同一个坐标，那么它们之间的曼哈顿距离为 0 0 0。
输入格式
第一行一个整数 T T T表示测试用例个数。 ( 1 ≤ T ≤ 1000 ) (1 \le T \le 1000) (1≤T≤1000)
对于每组测试用例：
一行一个整数 n ( 2 ≤ n ≤ 1 0 3 ) n(2 \le n \le 10^3) n(2≤n≤103)。
接下来 n n n行，第 i i i行表示第 i i i个自助店的坐标 ( x i , y i ) , ( − 1 0 9 ≤ x i , y i ≤ 1 0 9 ) (x_i, y_i), (-10^9 \le x_i, y_i \le 10^9) (xi,yi),(−109≤xi,yi≤109)。
数据保证 ∑ n ≤ 1 0 3 \sum n \le 10^3 ∑n≤103。
输出格式
对于每组测试用例，输出一个整数表示答案。
输入样例1
2
3
0 0
0 1
1 1
2
0 0
1 1
输出样例1
2
1
解释
在样例 1 1 1中，共有 { 1 , 1 , 2 } \{1, 1, 2\} {1,1,2}三个曼哈顿距离，共 2 2 2种。
题解
枚举所有点对，计算其曼哈顿距离后放入 s e t set set中计算 s i z e size size，或放入数组中排序去重。
#include <bits/stdc++.h>
using namespace std;
using ll = long long;const int N = 1e3 + 9;ll x[N], y[N];ll getabs(ll x) { return x < 0 ? -x : x; }void solve()
{int n;cin >> n;for (int i = 1; i <= n; ++i)cin >> x[i] >> y[i];set<ll> st;for (int i = 1; i <= n; ++i)for (int j = i + 1; j <= n; ++j){st.insert(getabs(x[i] - x[j]) + getabs(y[i] - y[j]));}cout << st.size() << '\n';
}int main()
{ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);int _;cin >> _;while (_--)solve();return 0;
}