给n个点的坐标,求能组合的等腰三角形个数
时间: 2023-05-24 14:05:55 浏览: 59
我们可以对于每一对点,计算它们之间的距离,然后将所有距离存储在一个数组中。对于每一个距离,我们需要再遍历一遍数组,计算有多少个距离等于它,然后将这个数量累加到结果中。具体地,我们可以使用哈希表来快速查询距离等于当前距离的点对数目。
时间复杂度为 $O(n^2\log n)$(排序代价)或 $O(n^2)$(哈希表代价)。
参考代码(使用哈希表):
```python
from collections import defaultdict
n = int(input())
points = [tuple(map(int, input().split())) for _ in range(n)]
distances = [((points[i][0]-points[j][0])**2+(points[i][1]-points[j][1])**2)**0.5
for i in range(n) for j in range(i+1, n)]
counts = defaultdict(int)
for d in distances:
counts[d] += 1
ans = 0
for c in counts.values():
ans += c*(c-1)//2 # 组合数公式
print(ans)
```
相关问题
给n个点的坐标,求能组合的等腰三角形个数,用c++实现
首先,可以通过计算每两个点之间的距离,将问题转换为求三条边长度相等的三角形的个数。
具体的,对于每一个点,遍历与其距离相等的所有点对,并计算它们之间的距离。将这些距离出现次数进行计数,保存在一个映射表中(可以使用 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;
}
```
给你n和坐标,求其中三个坐标能表示一个等腰三角形有多少种怎么写
题目描述:
给定n个平面上的点,求其中三个点能表示一个等腰三角形的方案数。
输入格式:
第一行包含整数n。
接下来n行,每行包含两个整数x和y,表示一个点的坐标。
输出格式:
输出一个整数,表示答案。
数据范围:
1≤n≤1000,
坐标的绝对值不超过10000。
输入样例:
5
0 0
0 1
0 3
0 7
0 10
输出样例:
15
解题思路:
找到每一个点和其他点之间的距离,并记录在map中。
for(int i=0; i<n; i++)
for(int j=i+1; j<n; j++)
先去做掉i和j之间的距离,记录下同一个距离出现过几次。每个距离对应的点的个数记作cnt,那么可以组成的等腰三角形个数就是cnt*(cnt-1)/2,因为对于一个距离而言,有cnt个点与它相等,则每一对搭配都能组成一个等腰三角形,计算组合即可。
最后所有的结果加起来就是最终答案。
C++ 代码
相关推荐
![doc](https://img-home.csdnimg.cn/images/20210720083327.png)
![rar](https://img-home.csdnimg.cn/images/20210720083606.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)