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;
}

相关问题

C++ O(n^2)求解给定 n 个坐标，求其中 3 个坐标能表示一个等腰三角形的组数

思路：

暴力枚举每三个坐标，然后判断它们是否能组成等腰三角形，时间复杂度为 O(n^3)。可以通过优化，降低时间复杂度。

枚举每个点作为等腰三角形的顶点，然后通过枚举另外两个点，判断它们到顶点的距离是否相等，如果相等就说明它们能组成等腰三角形。

具体实现：

先将所有坐标按照x坐标递增排序，如果x坐标相同，按照y坐标递增排序，这样能保证枚举点的顺序。

使用两层循环枚举每个点，然后再使用一层循环枚举另外两个点，如果它们到顶点的距离相等，则统计等腰三角形的个数。

由于题目中是三个点组成一个等腰三角形，所以不需要考虑点的排列组合的情况。

时间复杂度为 O(n^2)，空间复杂度为 O(1)。

代码实现：

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)。

用C++写 O(n^2)求解给定 n 个坐标，求其中 3 个坐标能表示一个等腰三角形的组数

#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;
}