用C++写 O(n^2)求解给定 n 个坐标,求其中 3 个坐标能表示一个等腰三角形的组数
时间: 2023-05-25 07:03:01 浏览: 67
#include <stdio.h>
int main() {
int n;
scanf("%d", &n); // 输入点的个数
int x[n], y[n]; // 存储点的横纵坐标
for (int i = 0; i < n; i++) {
scanf("%d%d", &x[i], &y[i]);
}
int cnt = 0; // 记录等腰三角形的组数
// 枚举三个点
for (int i = 0; i < n; i++) {
for (int j = i + 1; j < n; j++) {
for (int k = j + 1; k < n; k++) {
// 判断能否构成等腰三角形
if ((x[i] - x[j]) * (y[i] - y[k]) == (x[i] - x[k]) * (y[i] - y[j])) {
cnt++;
}
}
}
}
printf("%d\n", cnt);
return 0;
}
相关问题
C++ O(n^2)求解给定 n 个坐标,求其中 3 个坐标能表示一个等腰三角形的组数
思路:
暴力枚举每三个坐标,然后判断它们是否能组成等腰三角形,时间复杂度为 O(n^3)。可以通过优化,降低时间复杂度。
枚举每个点作为等腰三角形的顶点,然后通过枚举另外两个点,判断它们到顶点的距离是否相等,如果相等就说明它们能组成等腰三角形。
具体实现:
先将所有坐标按照x坐标递增排序,如果x坐标相同,按照y坐标递增排序,这样能保证枚举点的顺序。
使用两层循环枚举每个点,然后再使用一层循环枚举另外两个点,如果它们到顶点的距离相等,则统计等腰三角形的个数。
由于题目中是三个点组成一个等腰三角形,所以不需要考虑点的排列组合的情况。
时间复杂度为 O(n^2),空间复杂度为 O(1)。
代码实现:
```python
def count_isosceles_triangles(points):
n = len(points)
points.sort()
count = 0
for i in range(n):
for j in range(i+1, n):
d = points[j][0] - points[i][0]
if d % 2 == 1: # x坐标差为奇数,不能构成等腰三角形
continue
x = (points[i][0] + points[j][0]) / 2
for k in range(j+1, n):
if points[k][0] == x and points[k][1] != points[i][1] and points[k][1] != points[j][1]: # 满足横坐标相等,纵坐标不同
count += 1
return count
```
可以先对所有点按照 x 坐标排序,然后,对于固定的两个点,如果它们的 x 坐标的差为奇数,那么它们无法形成等腰三角形(因为等腰三角形的腰长必须是偶数)。如果它们的 x 坐标差为偶数,那么中间的那个点一定存在,且满足它的 x 坐标为两个点的 x 坐标的平均数。
找到了这个点之后,再检查它和这两个点的纵坐标不同,因为题目要求三点不共线。
这段代码中,三重循环,那么时间复杂度最高的就是轮询去重,也就是 O(N^2)。最好情况下,是遇到奇数个 X 坐标的点,过滤掉了根本组不成任何等腰三角形的点,那么可以达到 O(N) 的时间复杂度。最坏情况下,是偶数个 X 坐标的点比较多,在过滤掉之后,需要再 for 一次,这样总体时间复杂度就是 O(N^2)。
O(n^2)求解给定 n 个坐标,求其中 3 个坐标能表示一个等腰三角形的组数,用C++写
#include <stdio.h>
struct Point {
int x, y;
};
int main() {
int n;
scanf("%d", &n);
// 读入坐标
Point points[n];
for (int i = 0; i < n; i++) {
scanf("%d%d", &points[i].x, &points[i].y);
}
// 枚举三个点
int ans = 0;
for (int i = 0; i < n; i++) {
for (int j = i + 1; j < n; j++) {
for (int k = j + 1; k < n; k++) {
// 判断是否是等腰三角形
if ((points[i].x - points[j].x) * (points[i].y - points[k].y) ==
(points[i].x - points[k].x) * (points[i].y - points[j].y)) {
ans++;
}
}
}
}
printf("%d\n", ans);
return 0;
}