【数学】【计算几何】1453. 圆形靶内的最大飞镖数量

作者推荐

视频算法专题

本文涉及知识点

数学计算几何

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
-10⁴ <= xi, yi <= 10⁴
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);//计算hdouble 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

我想对大家说的话
闻缺陷则喜是一个美好的愿望，早发现问题，早修改问题，给老板节约钱。
子墨子言之：事无终始，无务多业。也就是我们常说的专业的人做专业的事。
如果程序是一条龙，那算法就是他的是睛