每日coding

447、回旋镖的数量

给定平面上?n 对 互不相同 的点?points ，其中 points[i] = [xi, yi] 。回旋镖 是由点?(i, j, k) 表示的元组 ，其中?i?和?j?之间的距离和?i?和?k?之间的欧式距离相等（需要考虑元组的顺序）。

返回平面上所有回旋镖的数量。

示例 1：

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

示例 2：

输入：points = [[1,1],[2,2],[3,3]]
输出：2

示例 3：

输入：points = [[1,1]]
输出：0

提示：

• n ==?points.length
• 1 <= n <= 500
• points[i].length == 2
• -104 <= xi, yi <= 104
• 所有点都 互不相同

这道题目原谅我第一时间没做出来，md，主要一看见这个就想全排列做，但是确实全排列做不出来，只能枚举的做法，就是一个一个试呗，这道题目说需要考虑元组的顺序，其实嘛，这个连接就是个V型，然后我们只需要找到V型的结点就行了，第二层for循环就找dis相同的就完事了。

class Solution {
public:
    int numberOfBoomerangs(vector<vector<int>>& points) {
        int ans = 0;
        for(const auto& point : points){
            unordered_map<int, int> map;
            double dis = 0.0;
            for(const auto& coordinate : points){
                dis = (point[0] - coordinate[0]) * (point[0] - coordinate[0]) + 
                      (point[1] - coordinate[1]) * (point[1] - coordinate[1]);
                ++map[dis];
            }
            for(const auto& [_, m] : map){
                ans += m * (m - 1);
            }
        }
        return ans;
    }
};

时间复杂度O（n^2）空间复杂度O（n）

补一个C++ limits头文件的用法（numeric_limits）

• https://www.cnblogs.com/For-her/p/3909307.html

今天开始更新计算数学，今天更新一个点到线段的距离

#include <iostream>
#include <cmath>

constexpr double kMinLength = 0.1;

struct Point{
  double x;
  double y;
};

struct LineSegment{
  Point p1;
  Point p2;
};

double distance(const Point& p1, const Point& p2){
  return std::sqrt((p1.x - p2.x) * (p1.x - p2.x) + (p1.y - p2.y) * (p1.y - p2.y));
}

double distanceToLineSegment(const Point& p, const LineSegment& l){
  double len = distance(l.p1, l.p2);
  if(len < kMinLength){
    return distance(p, l.p1);
  }
  double r = ((p.x - l.p1.x) * (l.p2.x - l.p1.x) + (p.y - l.p1.y) * (l.p2.y - l.p1.y)) / (len * len);
  if (r <= 0){ 
      return distance(p, l.p1);
  } else if(r >= 1){ 
      return distance(p, l.p2);
  } else{ 
      Point foot = { l.p1.x + r * (l.p2.x - l.p1.x), l.p1.y + r * (l.p2.y - l.p1.y) };
      return distance(p, foot);
  }
}

int main() {
    Point p = { 2, 3 };
    LineSegment l = { { 0, 0 }, { 4, 4 } };

    double dist = distanceToLineSegment(p, l);

    std::cout << "Distance from point to line segment: " << dist << std::endl;

    return 0;
}