Leetcode 447. 回旋镖的数量

题目描述

给定平面上 n 对不同的点，“回旋镖” 是由点表示的元组 (i, j, k) ，其中 i 和 j 之间的距离和 i 和 k 之间的距离相等（需要考虑元组的顺序）。

找到所有回旋镖的数量。你可以假设 n 最大为 500，所有点的坐标在闭区间 [-10000, 10000] 中。

示例 1:

输入: [[0,0],[1,0],[2,0]]

输出: 2

解释: 两个回旋镖为 [[1,0],[0,0],[2,0]] 和 [[1,0],[2,0],[0,0]]

解法

根据题意可知，数组中存在 n 个不同的点，以数组中某一个点为中心，若存在两个点到该中心点的距离相同，则存在两个回旋镖(因为考虑了回旋镖的点顺序)。

所以不妨求出数组中每个点到中心点的距离，若存在 x 个点到该中心点的距离相同，则存在 x*(x-1) 个回旋镖。

class Solution:
    def numberOfBoomerangs(self, points: List[List[int]]) -> int:
        ret=0
        d=dict()
        for x,y in points:
            for x1,y1 in points:
                dis=(x1-x)**2+(y1-y)**2
                d[dis]=d.get(dis,0)+1
            for n in d.values():
                ret+=n*(n-1)
            d.clear()
        return ret