LeetCode 447 号

class Solution
{
  public:       int numberOfBoomerangs(vector<pair<int,int>>&points)       {           int res = 0;           for (int i = 0; i < points.size(); ++i)           {               unordered_map<int, int>record;               for (int j = 0; j < pints.size(); j++)               {                   if (j != i)                       record[dis(points[i], points[j])] += 1;               }               for (unordered_map<int, int>::iterator iter = record.begin(); iter != record.end(); iter++)               {                   res+=(iter->second)*(iter->second - 1);               }           }           return res;       }
  private:       int dis(const pair<int, int>& pa, const pair<int, int>&pb)       {           return (pa.first - pb.first)*(pa.first - pb.first) + (pa.second - pb.second)*(pa.second - pb.second);       }
};

n 最大为 500，可以使用时间复杂度为 O(n^2)的算法。

• 遍历所有的点，让每个点作为一个锚点

• 然后再遍历其他的点，统计和锚点距离相等的点有多少个

• 然后分别带入 n(n-1) 计算结果并累加到 res 中

注意点：

• 如果有一个点a，还有两个点 b 和 c ，如果 ab 和 ac 之间的距离相等，那么就有两种排列方法 abc 和 acb ；

• 如果有三个点b，c，d 都分别和 a 之间的距离相等，那么有六种排列方法，abc, acb, acd, adc, abd, adb；

• 如果有 n 个点和点 a 距离相等，那么排列方式为 n(n-1)；

• 计算距离时不进行开根运算, 以保证精度；

• 只有当 n 大于等于 2 时，res 值才会真正增加，因为当n=1时，增加量为1 * ( 1 - 1 ) = 0 。