Number of Boomerangs

Givennpoints in the plane that are all pairwise distinct, a "boomerang" is a tuple of points(i, j, k)such that the distance betweeniandjequals the distance betweeniandk(the order of the tuple matters).

Find the number of boomerangs. You may assume thatnwill be at most 500 and coordinates of points are all in the range [-10000, 10000] (inclusive).

Example:

Input:

[[0,0],[1,0],[2,0]]


Output:

2


Explanation:

The two boomerangs are 
[[1,0],[0,0],[2,0]]
 and 
[[1,0],[2,0],[0,0]]

Summary:

定义一种类似“回形标”的三元组结构，即在三元组(i, j, k)中i和j之间的距离与i和k之间的距离相等。找到一组坐标数据中，可构成几组这样的“回形标”结构。

Analysis:

若在一组点集{a, b, c, d, ...}中，以点a为一个端点，与dis(a, b)相等的点存在n个（包含点b），那么在这n个点中任意选出两个点与点a构成三元组，则有n(n - 1) / 2种情况。但因为三元组[a, b, c]与三元组[a, c, b]并不相同，所以实际为排列问题，答案为n(n - 1)。

代码中正是以此为基本思想，变成了遍历所有点，让每个点都做一次点a，与其余点共组成多少种不同的距离，此处用map记录，key为距离长度，value为距离出现次数。再根据前面的公式计算即可。

class Solution(object):
    def numberOfBoomerangs(self, points):
        """
        :type points: List[List[int]]
        :rtype: int
        """
        ans = 0
        for x1, y1 in points:
            dmap = collections.defaultdict(int)
            for x2, y2 in points:
                dmap[(x1 - x2) ** 2 + (y1 - y2) ** 2] += 1
            for d in dmap:
                ans += dmap[d] * (dmap[d] - 1)
        return ans