给定 � n 个坐标,求其中 3 3 个坐标能表示一个等腰三角形的组数。 三点共线不算三角形,等边三角形为特殊的等腰三角形。 输入描述:第一行输入n,接下来2 - n + 1 行每行输入一个坐标。( 0 < n <= 2000)保证没有重复坐标
时间: 2024-03-24 09:39:45 浏览: 17
以下是一份C++的代码实现,时间复杂度为O(n^2):
```
#include <iostream>
#include <vector>
#include <map>
#include <cmath>
using namespace std;
struct Point {
int x, y;
bool operator==(const Point& p) const {
return x == p.x && y == p.y;
}
};
struct Hash {
size_t operator()(const Point& p) const {
return p.x ^ p.y;
}
};
int main() {
int n;
cin >> n;
vector<Point> points(n);
for (int i = 0; i < n; i++) {
cin >> points[i].x >> points[i].y;
}
int count = 0;
for (int i = 0; i < n; i++) {
// 使用哈希表记录每个斜率出现的次数
map<double, int> slopeCount;
for (int j = i + 1; j < n; j++) {
if (points[i] == points[j]) {
continue;
}
// 计算两个点之间的距离
int dx = points[i].x - points[j].x;
int dy = points[i].y - points[j].y;
double distance = sqrt(dx * dx + dy * dy);
// 计算两个点之间的斜率
double slope = (dx == 0) ? INFINITY : (double)dy / dx;
// 更新哈希表
if (slopeCount.find(slope) == slopeCount.end()) {
slopeCount[slope] = 0;
}
count += slopeCount[slope];
slopeCount[slope]++;
}
}
cout << count << endl;
return 0;
}
```
具体实现思路与之前给出的思路相似,不同之处在于使用了哈希表来记录每个斜率出现的次数,从而避免了枚举每一组可能的三个点的组合。同时,为了避免三点共线的情况,使用了一个自定义的Point结构体和Hash函数来实现哈希表的键类型为Point类型,从而只有不重复的点才会被计算。
相关推荐
![zip](https://img-home.csdnimg.cn/images/20210720083736.png)
![doc](https://img-home.csdnimg.cn/images/20210720083327.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)