输出距圆心最远的圆内或边界上的积分点
Output integral point in or on the boundary of the circle which has the largest distance from the center
面试后，我有这个问题，但现在我没有什么好的解决办法。
给定一个二维平面上的圆
输出距离圆心最远的圆内或边界上的积分点。中心和半径的坐标是浮点数。
有大牛能给我点建议吗？
如果您正在寻找起点，请不要害怕考虑 "a bad way that will probably work"。
这更像是一个 maths/logic 问题，而不是一个计算问题，一旦你知道如何 "by hand" 给定无限时间，用编程语言实现它应该是解决方案中比较简单的部分。
例如...
我们的策略可以是：
枚举正方形包围圆圈的所有"integral points"（效率低下，但考虑到这一点至少会让你的大脑运转起来）。
1)
编写一个函数，输出这个正方形中所有点的列表。
在 C++ 中，您可能想要实现
struct IntPoint{ int x; int y; };
std::vector<IntPoint> getPointsAroundCircle(float center, float radius);
2) 遍历所有的点。
找出这些点中的哪些点实际上在（/上）圆圈中，以及 "remember" 哪个点的距离最大。您可能想要实现以下辅助函数：
float distance(float center, float radius, const IntPoint & p);
提示：知道点到圆心的距离如何帮助我们确定它是否在圆内？
注意：涉及 floats/doubles 的计算（或更确切地说是比较）需要进行四舍五入。您可能希望使用某种 "epsilon" 作为容差进行比较。
如果您有兴趣，请阅读 material：
https://randomascii.wordpress.com/2012/02/25/comparing-floating-point-numbers-2012-edition/
3) 遍历所有点后，您将知道要打印哪个点的 x、y 坐标。
假设您的圆在 (X,Y) 处，半径为 R。
1) 生成所有可能的 x 的列表：
xList=[ceil(X-R):1:floor(X+R)]
2) 搜索潜在的 ys:
yUpperList=Y+sqrt(R^2 - (xList-X).^2)
yLowerList=Y-sqrt(R^2 - (xList-X).^2)
3) 将 y 个候选人缩减为整数
yUpperList = floor(yUpperList)
yLowerList = ceil(yLowerList)
4) 重新计算距离
distance=sqrt([yUpperList;yLowerList].^2 + [xList;xList].^2)
5) 求最大距离：
maxDistance = max(distance(:))
这会给您带来 O(R) 的复杂性。
我想解决方案的大小与 R 呈线性关系，所以我认为您不能做得更好。
面试后，我有这个问题，但现在我没有什么好的解决办法。
给定一个二维平面上的圆 输出距离圆心最远的圆内或边界上的积分点。中心和半径的坐标是浮点数。 有大牛能给我点建议吗？
如果您正在寻找起点，请不要害怕考虑 "a bad way that will probably work"。
这更像是一个 maths/logic 问题，而不是一个计算问题，一旦你知道如何 "by hand" 给定无限时间，用编程语言实现它应该是解决方案中比较简单的部分。
例如...
我们的策略可以是：
枚举正方形包围圆圈的所有"integral points"（效率低下，但考虑到这一点至少会让你的大脑运转起来）。
1) 编写一个函数，输出这个正方形中所有点的列表。 在 C++ 中，您可能想要实现
struct IntPoint{ int x; int y; };
std::vector<IntPoint> getPointsAroundCircle(float center, float radius);
2) 遍历所有的点。 找出这些点中的哪些点实际上在（/上）圆圈中，以及 "remember" 哪个点的距离最大。您可能想要实现以下辅助函数：
float distance(float center, float radius, const IntPoint & p);
提示：知道点到圆心的距离如何帮助我们确定它是否在圆内？
注意：涉及 floats/doubles 的计算（或更确切地说是比较）需要进行四舍五入。您可能希望使用某种 "epsilon" 作为容差进行比较。 如果您有兴趣，请阅读 material： https://randomascii.wordpress.com/2012/02/25/comparing-floating-point-numbers-2012-edition/
3) 遍历所有点后，您将知道要打印哪个点的 x、y 坐标。
假设您的圆在 (X,Y) 处，半径为 R。
1) 生成所有可能的 x 的列表：
xList=[ceil(X-R):1:floor(X+R)]
2) 搜索潜在的 ys:
yUpperList=Y+sqrt(R^2 - (xList-X).^2)
yLowerList=Y-sqrt(R^2 - (xList-X).^2)
3) 将 y 个候选人缩减为整数
yUpperList = floor(yUpperList)
yLowerList = ceil(yLowerList)
4) 重新计算距离
distance=sqrt([yUpperList;yLowerList].^2 + [xList;xList].^2)
5) 求最大距离：
maxDistance = max(distance(:))
这会给您带来 O(R) 的复杂性。
我想解决方案的大小与 R 呈线性关系，所以我认为您不能做得更好。