回旋镖的数量

题目描述

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

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

示例:

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

分析

遍历，以当前的节点为轴，使用map统计跟当前节点距离一样的数量。map的key是距离，value是数量
再遍历统计的结果，计算结果,计算的方式是:数量c, c * (c - 1)。表示c个节点中取任意两个的排列数。
示例中：
跟1距离相等的个数是2,2*(2 - 1) = 2

代码

class Solution {
public:
    int getDis(pair<int,int> &a, pair<int, int> &b){
        int x = b.first - a.first;
        int y = b.second - a.second;
        return x * x + y * y;
    }
    
    int numberOfBoomerangs(vector<pair<int, int>>& points) {
        int ans = 0;
        for(int i = 0; i < points.size(); i++){
            unordered_map<int,int> m; //统计与i同距离的个数
            for(int j = 0; j < points.size(); j++){
                if(i==j) {
                    continue;
                }
                int d = getDis(points[i], points[j]);
                ++m[d];
            }
            for(auto& it:m) {
                if(it.second < 2) {
                    continue;
                }
                ans += it.second * (it.second - 1);
            }
        }
        return ans;
    }
};

题目链接

https://leetcode-cn.com/problems/number-of-boomerangs/description/