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