【数学】【计算几何】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);
	//计算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

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