hiho一下第111周《Farthest Point》题目分析

7
1

题目大意

给定平面直角坐标系中的一个圆,求圆内(可以在边界上)离圆心最远的整点。

解题思路

本题是一道简单的计算几何类题目。

要求园内的整点,即xy坐标均为整数的点,首先我们需要求出可能的xy的范围。

先考虑x,显然x的上下界分别为x+rx-r

由于题目给定的xr均为实数,因此x+rx-r也可能不为整数。

所以实际上包含在圆内的x坐标上下界分别为floor(x+r)ceil(x-r)。(floor表示下取整,ceil表示上取整)

在确定了x以后,其对应的y坐标范围也可以随之确定。如下图所示,根据勾股定理,我们即可求出d的长度。

同时可以得到对应的y坐标上下界为y+dy-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 左边的坐标也有可能是正数啊

  • 添加评论
  • reply

4 answer(s)

0

各位要用double啊!

  • 兄台,在for循环里面,你的len一直是0啊,一直没有更新啊,所以smalls函数一直返回true,那么最后的结果就是你测试的最后一个数据了。。。

  • 添加评论
  • reply
0

WA请问是哪里有问题?研究好久了

 #include<iostream>
    #include<math.h>
    using namespace std;

    bool smalls(double x,double y){
        double eps=1e-6;
        if(x-y<=eps) return true;
        else return false;
    }

    int main(){
        //freopen("in.txt","r",stdin);
        double x,y,r,d;
        int i;
        int ax,ay;
        double len=0;
        cin>>x>>y>>r;
        ax=x; ay=y;
        for(i=ceil(x-r);i<=floor(x+r);i++){
           d=sqrt(r*r-(i-x)*(i-x));
          int  ymax=floor(y+d);
          int  ymin=ceil(y-d);
            if(smalls(len,((i-x)*(i-x)+(ymax-y)*(ymax-y)))){
                ax=i; ay=ymax;
              }
            if(smalls(len,((i-x)*(i-x)+(ymin-y)*(ymin-y)))){
                ax=i; ay=ymin;
              }
        }
        cout<<ax<<" "<<ay;
        return 0;
    }
0

可以

0

Nice

write answer 切换为英文 切换为中文


转发分享