【数学知识】LCP42: 玩具套圈

2023-12-15 15:33:08

作者推荐

【动态规划】【广度优先搜索】LeetCode:2617 网格图中最少访问的格子数

本文涉及的基础知识点

优化后,就不需要二分了。

二分查找算法合集

题目

「力扣挑战赛」场地外,小力组织了一个套玩具的游戏。所有的玩具摆在平地上,toys[i] 以 [xi,yi,ri] 的形式记录了第 i 个玩具的坐标 (xi,yi) 和半径 ri。小扣试玩了一下,他扔了若干个半径均为 r 的圈,circles[j] 记录了第 j 个圈的坐标 (xj,yj)。套圈的规则如下:
若一个玩具被某个圈完整覆盖了(即玩具的任意部分均在圈内或者圈上),则该玩具被套中。
若一个玩具被多个圈同时套中,最终仅计算为套中一个玩具
请帮助小扣计算,他成功套中了多少玩具。
注意:
输入数据保证任意两个玩具的圆心不会重合,但玩具之间可能存在重叠。
示例 1:
输入:toys = [[3,3,1],[3,2,1]], circles = [[4,3]], r = 2
输出:1
解释: 如图所示,仅套中一个玩具
示例 2:
输入:toys = [[1,3,2],[4,3,1],[7,1,2]], circles = [[1,0],[3,3]], r = 4
输出:2
解释: 如图所示,套中两个玩具image.png
参数范围
1 <= toys.length <= 104
0 <= toys[i][0], toys[i][1] <= 109
1 <= circles.length <= 104
0 <= circles[i][0], circles[i][1] <= 109
1 <= toys[i][2], r <= 10

分析

圆的关系

圆和圆的关系分以下几种:

相离圆心距离大于半径之和没套中
外切圆新距离等与半径和没套中
相交圆心距在(半径差,半径和)没套中
内切圆心距等于半径之差套中
内含圆心距小于半径之差套中
重合心距等于半径之差套中

套中的条件:圆心距小于等于半径之差。注意:套的半径必须大于等于玩具。

枚举什么

枚举玩具和套,时间复杂度O(108),超时。可以枚举玩具和套的中心,这样复杂度就降到o(10^6)。

变量

setCircleRC所有套的中心,中心相同的套忽略
vPoints假定玩具中心在(0,0),套中心在那儿,可以包括玩具中心

代码

核心代码

class Solution {
public:
	int circleGame(vector<vector<int>>& toys, vector<vector<int>>& circles, int r) {
		unordered_set<long long> setCircleRC;
		for (const auto& v : circles)
		{
			setCircleRC.emplace(v[0]* m_llUnit +v[1]);
		}
		vector<pair<int, int>> vPoints;
		for (int x = -r; x <= r; x++)
		{
			for (int y = -r; y <= r; y++)
			{
				if (x * x + y * y <= r * r)
				{
					vPoints.emplace_back(x, y);
				}
			}
		}
		int iRet = 0;
		for (const auto& v : toys)
		{
			if (v[2] > r)
			{
				continue;
			}
			bool is = false;
			for (const auto& [x, y] : vPoints)
			{
				const int iDis2 = x * x + y * y;
				if (iDis2 > (r - v[2]) * (r - v[2]))
				{
					continue;
				}
				is |= setCircleRC.count((v[0]+x) * m_llUnit + (v[1]+y));
			}
			iRet += is;
		}
		return iRet;
	}
	const long long m_llUnit = 10'000'000'000;
};

测试用例


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]);
	}
}

template<class T>
void Assert(const T& t1, const T& t2)
{
	assert(t1 == t2);
}

int main()
{
	vector<vector<int>> toys, circles;
	int r;
	{
		Solution slu;		
		toys = { {3,3,1},{3,2,1} }, circles = { {4,3} }, r = 2;
		auto res = slu.circleGame(toys,circles,r);
		Assert(1, res);
	}
	{
		Solution slu;
		toys = { {1,3,2},{4,3,1},{7,1,2} }, circles = { {1,0},{3,3} }, r = 4;
		auto res = slu.circleGame(toys, circles, r);
		Assert(2, res);
	}
}

2023年3月

class Solution {
public:
	int circleGame(vector<vector<int>>& toys, vector<vector<int>>& circles, int r) {
		std::unordered_set<long long> mCircleXY;
		for (const auto& v : circles)
		{
			mCircleXY.insert(m_llMul*v[0] + v[1]);
		}
		int iRet = 0;
		for (const auto& toy : toys)
		{
			if (toy[2] > r)
			{
				continue;
			}
			long long iMaxDis2 = (long long)(r - toy[2])*(r - toy[2]);
			int iMaxDis = sqrt(iMaxDis2) + 0.5;
			
			bool bCan = false;
			for (int x = toy[0] - iMaxDis; x <= toy[0] + iMaxDis; x++)
			{
				for (int y = toy[1] - iMaxDis; y <= toy[1] + iMaxDis; y++)
				{
					const long long iCurDis2 = (long long)(x - toy[0])*(x - toy[0]) + (long long)(y - toy[1])*(y - toy[1]);
					if (iCurDis2 > iMaxDis2)
					{
						continue;
					}
					const long long llMask = m_llMul*x + y;
					if (mCircleXY.count(llMask))
					{
						bCan = true;
						break;
					}
				}
				if (bCan)
				{
					break;
				}
			}
			if (bCan)
			{
				iRet++;
			}
		}
		return iRet;
	}
	const long long m_llMul = 1000 * 1000 * 1000 * 2;
};

扩展阅读

视频课程

有效学习:明确的目标 及时的反馈 拉伸区(难度合适),可以先学简单的课程,请移步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++**实现。

文章来源:https://blog.csdn.net/he_zhidan/article/details/135001046
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。