给n个点的坐标,求能组合的等腰三角形个数,用c++实现
时间: 2023-05-25 17:02:29 浏览: 58
首先,可以通过计算每两个点之间的距离,将问题转换为求三条边长度相等的三角形的个数。
具体的,对于每一个点,遍历与其距离相等的所有点对,并计算它们之间的距离。将这些距离出现次数进行计数,保存在一个映射表中(可以使用 C++ STL 中的 map 或者 unordered_map),然后对于每个长度为 d 的边,取出映射表中对应的出现次数 c,那么以该边为底的等腰三角形的个数就是 c * (c-1) / 2。
最后将所有边的贡献加起来,即为答案。
以下是 C++ 的代码实现:
```c++
#include <iostream>
#include <map>
#include <vector>
using namespace std;
typedef pair<int, int> Point;
int main() {
int n;
cin >> n;
vector<Point> points(n);
for (int i = 0; i < n; i++) {
cin >> points[i].first >> points[i].second;
}
int ans = 0;
for (int i = 0; i < n; i++) {
map<int, int> dist_count; // 距离出现次数的映射表
for (int j = 0; j < n; j++) {
if (j == i) continue;
int dx = points[i].first - points[j].first;
int dy = points[i].second - points[j].second;
int dist = dx * dx + dy * dy;
dist_count[dist]++;
}
for (auto& p : dist_count) { // 遍历映射表中的每个长度 d
int d = p.first;
int c = p.second;
if (c < 2) continue;
ans += c * (c-1) / 2;
}
}
cout << ans << endl;
return 0;
}
```
相关推荐
![pdf](https://img-home.csdnimg.cn/images/20210720083512.png)
![cpp](https://img-home.csdnimg.cn/images/20210720083646.png)
![zip](https://img-home.csdnimg.cn/images/20210720083736.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)