本文涉及知识点
数学 计算几何
LeetCoce:1453. 圆形靶内的最大飞镖数量
Alice 向一面非常大的墙上掷出 n 支飞镖。给你一个数组 darts ，其中 darts[i] = [xi, yi] 表示 Alice 掷出的第 i 支飞镖落在墙上的位置。
Bob 知道墙上所有 n 支飞镖的位置。他想要往墙上放置一个半径为 r 的圆形靶。使 Alice 掷出的飞镖尽可能多地落在靶上。
给你整数 r ，请返回能够落在 任意 半径为 r 的圆形靶内或靶上的最大飞镖数。
示例 1 ：
输入：darts = [[-2,0],[2,0],[0,2],[0,-2]], r = 2
输出：4
解释：如果圆形靶的圆心为 (0,0) ，半径为 2 ，所有的飞镖都落在靶上，此时落在靶上的飞镖数最大，值为 4 。
示例 2 ：
输入：darts = [[-3,0],[3,0],[2,6],[5,4],[0,9],[7,8]], r = 5
输出：5
解释：如果圆形靶的圆心为 (0,4) ，半径为 5 ，则除了 (7,8) 之外的飞镖都落在靶上，此时落在靶上的飞镖数最大，值为 5 。
提示：
1 <= darts.length <= 100
darts[i].length == 2
-104 <= xi, yi <= 104
darts 中的元素互不相同
1 <= r <= 5000
计算几何
至少可以圈一个飞镖。我们来考虑两个或更多飞镖。
假定圆C可以圈n(n>1)个飞镖，我们轻微移动圆C，使得一个或多个飞镖从圆内移到圆上，令新圆为C1。如果有两个或更多的飞镖在圆上，则C2=C1。如果只有一个飞镖在圆上，假定此飞镖在A，保持A点不动，旋转圆C1,使得有一个到多个飞镖从圆内转到圆上，令新转到圆上的任意一个飞镖为B，新圆为C2。 → \rightarrow→ 只需要枚举两个飞镖都在圆上的圆。
枚举不同的飞镖A,B，有两个圆心都要枚举。AB的时候枚举一个，BA的时候枚举另外一个。
代码
struct vec; struct point { point operator+(const vec& v); double x, y; point(double i, double j) :x(i), y(j) {} }; struct vec { vec(double tx, double ty) { x = tx; y = ty; } vec(const point& from, const point& to) { x = to.x - from.x; y = to.y - from.y; } double x; double y; vec RatotaPlus90() { return { -y,x }; } void ChangeToUint() { double len = sqrt(x * x + y * y); x /= len; y /= len; } vec& operator*=(double d) { x *= d; y *= d; return *this; } }; point point::operator+(const vec& v) { return { x + v.x,y + v.y }; } //算两点距离 double dist(const point& a , const point& b) { return sqrt((a.x - b.x) * (a.x - b.x) + (a.y - b.y) * (a.y - b.y)); } //计算圆心 point CircleCenter(point& a, point& b, int r) { //算中点 point mid((a.x + b.x) / 2.0, (a.y + b.y) / 2.0); //AB距离的一半 double d = dist(a, mid); //计算h double h = sqrt(r * r - d * d); //计算垂线 vec ba(a, b); vec hd = ba.RatotaPlus90(); hd.ChangeToUint(); hd *= h; return mid + hd; } class Solution { public: int numPoints(vector<vector<int>>& darts, int r) { int iCnt = 1; for (int i = 0; i < darts.size(); i++) { for (int j = 0; j < darts.size(); j++) { if (i == j) { continue; } point a(darts[i][0], darts[i][1]), b(darts[j][0], darts[j][1]); if (dist(a, b) > r * 2) { continue; } auto ptCenter = CircleCenter(a, b, r); int iCurCnt = 0; for (const auto& v : darts) { point tmp(v[0], v[1]); const double dDis = dist(ptCenter, tmp); if (dDis <= r) { iCurCnt++; } } iCnt = max(iCnt, iCurCnt); } } return iCnt; } };
测试用例
template<class T,class T2> void Assert(const T& t1, const T2& t2) { assert(t1 == t2); } template<class T> void Assert(const vector<T>& v1, const vector<T>& v2) { if (v1.size() != v2.size()) { assert(false); return; } for (int i = 0; i < v1.size(); i++) { Assert(v1[i], v2[i]); } } int main() { vector<vector<int>> darts; int r = 0; { Solution sln; darts = { {-8,9},{-2,1},{4,-4},{10,10},{-6,0},{-8,4},{-10,8},{-1,-2} }, r =11; auto res = sln.numPoints(darts, r); Assert(8, res); } { Solution sln; darts = { {-2,0},{2,0},{0,2},{0,-2} }, r = 2; auto res = sln.numPoints(darts, r); Assert(4, res); } { Solution sln; darts = { {-3,0},{3,0},{2,6},{5,4},{0,9},{7,8} }, r = 5; auto res = sln.numPoints(darts, r); Assert(5, res); } }
2023年6月
struct point{ double x, y; point(double i, double j) :x(i), y(j){} }; //算两点距离 double dist(double x1, double y1, double x2, double y2){ return sqrt((x1 - x2)(x1 - x2) + (y1 - y2)(y1 - y2)); } //计算圆心 point CircleCenter(point& a, point& b, int r){ //算中点 point mid((a.x + b.x) / 2.0, (a.y + b.y) / 2.0); //AB距离的一半 double d = dist(a.x, a.y, mid.x, mid.y); //计算h double h = sqrt(rr - dd); //计算垂线 point ba(b.x - a.x, b.y - a.y); point hd(-ba.y, ba.x); double len = sqrt(hd.xhd.x + hd.yhd.y); hd.x /= len, hd.y /= len; hd.x *= h, hd.y *= h; return point(hd.x + mid.x, hd.y + mid.y); } class Solution { public: int numPoints(vector<vector>& darts, int r) { int iMaxNum = 1; for (int i = 0; i < darts.size(); i++) { point pt1 ( darts[i][0], darts[i][1] ); for (int j = 0; j < darts.size(); j++) { if (i == j) { continue; } // if (dist(darts[i][0], darts[i][1], darts[j][0], darts[j][1]) > 2*r) { continue; } point pt2(darts[j][0], darts[j][1]); //CircleCenter(pt1,pt2,r)和CircleCenter（pt2,pt1,r)的返回值不同 auto ptCenter = CircleCenter(pt1, pt2,r); int iNum = 0; for (const auto& v : darts) { if (dist(ptCenter.x, ptCenter.y, v[0], v[1]) > r) { continue; } iNum++; } iMaxNum = max(iMaxNum, iNum); } } return iMaxNum; } };
扩展阅读
视频课程
有效学习：明确的目标 及时的反馈 拉伸区（难度合适），可以先学简单的课程，请移步CSDN学院，听白银讲师（也就是鄙人）的讲解。
https://edu.csdn.net/course/detail/38771
如何你想快速形成战斗了，为老板分忧，请学习C#入职培训、C++入职培训等课程
https://edu.csdn.net/lecturer/6176
相关
下载
想高屋建瓴的学习算法，请下载《喜缺全书算法册》doc版
https://download.csdn.net/download/he_zhidan/88348653
| 我想对大家说的话 |
| 闻缺陷则喜是一个美好的愿望，早发现问题，早修改问题，给老板节约钱。 |
| 子墨子言之：事无终始，无务多业。也就是我们常说的专业的人做专业的事。 |
| 如果程序是一条龙，那算法就是他的是睛 |
测试环境
操作系统：win7 开发环境： VS2019 C++17
或者 操作系统：win10 开发环境： VS2022 C++17
如无特殊说明，本算法用**C++**实现。
