【算法入门教育赛2】C.曼哈顿种类 C++题解与代码

比赛地址：https://www.starrycoding.com/contest/6

题目描述

牢$e$知道在武汉有$n$家自助店，第$i$个自助店用坐标$(x_i,y_i)$表示，因为武汉的街道都是互相垂直的，现在他想知道所有自助店之间的曼哈顿距离有多少种？

曼哈顿距离：$(x_1,y_1)$与$(x_2,y_2)$的曼哈顿距离为：$|x_1-x_2|+|y_1-y_2|$。

注意：可能有多个自助点在同一个坐标，那么它们之间的曼哈顿距离为$0$。

输入格式

第一行一个整数$T$表示测试用例个数。$(1\le T\le 1000)$

对于每组测试用例：

一行一个整数$n(2\le n\le 10^3)$。

接下来$n$行，第$i$行表示第$i$个自助店的坐标$(x_i,y_i),(-10^9\le x_i,y_i\le 10^9)$。

数据保证$\sum n\le 10^3$。

输出格式

对于每组测试用例，输出一个整数表示答案。

输入样例1

2
3
0 0
0 1
1 1
2
0 0
1 1

输出样例1

2
1

解释

在样例$1$中，共有 { 1 , 1 , 2 } \{1, 1, 2\} {1,1,2}三个曼哈顿距离，共$2$种。

题解

枚举所有点对，计算其曼哈顿距离后放入$set$中计算$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;
}