链接:https://ac.nowcoder.com/acm/contest/59840/K 来源:牛客网 给定 � n 个坐标,求其中 3 3 个坐标能表示一个等腰三角形的组数。 三点共线不算三角形,等边三角形为特殊的等腰三角形。

这道题可以通过枚举任意三个点，判断它们能否组成等腰三角形来解决。具体方法是，计算其中两个点的距离，然后枚举第三个点，判断其与这两个点的距离是否相等。如果相等，则找到了一个等腰三角形。

需要注意的是，同一个等腰三角形可能会被多次计算，因此需要使用一些方法来避免重复计算。一种常用的方法是，对所有点按照横坐标排序，然后枚举每个点作为等腰三角形的中点，再枚举与该点横坐标相差不超过距离的点作为另外一个顶点，这样可以避免重复。

时间复杂度为 O(n^2 log n)，可以通过本题。

相关问题

链接：https://ac.nowcoder.com/acm/contest/59840/K 来源：牛客网 给定 � n 个坐标，求其中 3 3 个坐标能表示一个等腰三角形的组数。 三点共线不算三角形，等边三角形为特殊的等腰三角形。

这道题可以用哈希表来解决。首先枚举三角形的顶点，然后计算出这个顶点到其它点的距离，并将距离存入哈希表中。接着枚举其它点作为三角形的另一个顶点，计算出这个点到剩下的点的距离，并在哈希表中查找是否存在与之前顶点距离相等的点，如果存在，则说明这三个点可以组成等腰三角形。

具体实现可以使用 STL 中的 unordered_map 来实现哈希表。时间复杂度为 O(n^2)。

以下是代码实现：

链接：https://ac.nowcoder.com/acm/contest/59840/K 来源：牛客网 给定 n 个坐标，求其中 3 个坐标能表示一个等腰三角形的组数。 三点共线不算三角形，等边三角形为特殊的等腰三角形。

对于这道题，我们可以考虑对输入的每两个点求出它们的中点，然后把这个中点作为哈希表的键值，值为一个列表，存储所有能与该中点构成等腰三角形的点。具体做法如下：

1. 枚举每两个点，计算它们的中点，把该中点作为哈希表的键值，值为一个空列表。

2. 遍历所有点，如果该点与中点的距离等于某个已有中点的距离，则将该点加入到对应的列表中。

3. 对于每个中点对应的列表，如果列表长度大于等于2，则说明存在能与该中点构成等腰三角形的点，计算组合数并累加到答案中。

时间复杂度为 $O(n^2 \log n)$，其中 $n$ 为点的个数。具体实现细节可以参考下面的代码：

from collections import defaultdict
import math

n = int(input())
points = []
for i in range(n):
    x, y = map(int, input().split())
    points.append((x, y))

# 计算两点之间的距离
def dist(p1, p2):
    return math.sqrt((p1[0] - p2[0]) ** 2 + (p1[1] - p2[1]) ** 2)

# 构建哈希表
hash_map = defaultdict(list)
for i in range(n):
    for j in range(i + 1, n):
        p1, p2 = points[i], points[j]
        mid = ((p1[0] + p2[0]) / 2, (p1[1] + p2[1]) / 2)
        hash_map[mid] = []

# 遍历所有点
for i in range(n):
    for j in range(i + 1, n):
        p1, p2 = points[i], points[j]
        mid = ((p1[0] + p2[0]) / 2, (p1[1] + p2[1]) / 2)
        for k in range(n):
            if k != i and k != j:
                p3 = points[k]
                d1, d2 = dist(p1, p3), dist(p2, p3)
                if abs(d1 - d2) < 1e-6:
                    hash_map[mid].append(p3)

# 计算答案
ans = 0
for mid, points in hash_map.items():
    if len(points) >= 2:
        n = len(points)
        ans += n * (n - 1) // 2

print(ans)