题目大意
给定平面直角坐标系中的一个圆,求圆内(可以在边界上)离圆心最远的整点。
解题思路
本题是一道简单的计算几何类题目。
要求园内的整点,即x
和y
坐标均为整数的点,首先我们需要求出可能的x
和y
的范围。
先考虑x
,显然x
的上下界分别为x+r
和x-r
。
由于题目给定的x
和r
均为实数,因此x+r
和x-r
也可能不为整数。
所以实际上包含在圆内的x
坐标上下界分别为floor(x+r)
和ceil(x-r)
。(floor
表示下取整,ceil
表示上取整)
在确定了x
以后,其对应的y
坐标范围也可以随之确定。如下图所示,根据勾股定理,我们即可求出d
的长度。
同时可以得到对应的y
坐标上下界为y+d
至y-d
。显然这两个值也有可能不为整数。
因此实际的y
坐标范围为floor(y+d)
和ceil(y-d)
。
通过这两个步骤,我们就可以得到所有在圆内的点:
For tx = floor(x+r) .. ceil(x-r)
d = sqrt(r*r - (tx-x)*(tx-x)) // 勾股定理
For ty = floor(y+d) .. ceil(y-d)
// (tx, ty) 是在圆内的点
// 更新比较最优点
End For
End For
由于本题给定的r
长度最大为100,000,则可能出现在圆内的点最大可能为314亿个点。
直接枚举每个点来寻找最优值显然是不合理的,我们需要优化这个算法。
通过观察我们可以发现,在确定x
坐标之后,所有的y
坐标中越靠近两端的点一定比靠近中间的点离圆心远。
所以实际上我们只需要比较最两端的两个点,他们之中离圆心最远的点一定就是该x
坐标下离圆心最远的点。
因此改进算法为:
ret_x = x
ret_y = y
For tx = floor(x+r) .. ceil(x-r)
d = sqrt(r*r - (tx-x)*(tx-x)) // 勾股定理
// 由于要求最大值,我们先考虑y坐标较大的一边
ty = floor(y+d)
If (tx,ty) is better than (ret_x, ret_y) Then
ret_x = tx
ret_y = ty
End If
// 再考虑坐标值较小的一边
ty = ceil(y-d)
If (tx,ty) is better than (ret_x, ret_y) Then
ret_x = tx
ret_y = ty
End If
End For
使用改进的算法时间复杂度为O(R),可以顺利的通过所有的测试点。
关于精度问题
在计算几何的计算中,精度问题是一个很常见的问题。
这是由于计算机存储浮点数时保留的精度有限而产生的。
即使用两个实型变量来存储同一个数字,都有可能产生误差。
因此在判定实型变量大小关系时,若直接采用=
,>
或<
进行比较,很有可能出错。
一般常见的解决方法是设定一个极小量epsilon
(一般写作eps
)来辅助比较。
比如判定两个浮点数是否相等时,我们检查两个浮点数之间的差值。若差值小于eps
时,我们就认为这两个浮点数相等:
equals(double x, double y):
eps = 1e-6 // 根据题目要求的精度范围来设定eps
If (abs(x - y) < eps) Then
Return True
End If
Return false
同样,其它比较符号也需要做对应的修改,具体可以参考下表:
原符号 修正
a == b abs(a-b) < eps
a != b abs(a-b) > eps
a > b a-b > eps
a >= b a-b > -eps
a < b a-b < -eps
a <= b a-b < eps
题解说要 xi遍历ceil(x-r) 到 floor(x+r), 为什么不可以直接 int(x-r) 到 int(x+r) 这样取小数部分有错么?
这个样例难道不是5 4 最大?怎么会是6 1 呢
@mahome 左边的坐标也有可能是正数啊