0

下記AtCoder Contest 191のD問題について質問させていただきたいです。

問題文

2次元平面上に中心 (X,Y) 、半径 R の円があります。 この円の内部または周上にある格子点 (x,y座標がともに整数である点)
の個数を求めてください。

制約

  • |X|≤105
  • |Y|≤105
  • 0<R≤105
  • X,Y,Rは高々小数第 4 位まで与えられる

入力

入力は以下の形式で標準入力から与えられる。

X Y R

入力例 1

0.2 0.8 1.1

出力例 1

3

以下のような円になります。赤く印の付いた点が、この円の内部または周上にある格子点です。

入力例 2

100 100 1

出力例 2

5

X,Y,R には小数点が含まれないかもしれません。 円周上の格子点も数える対象に含むことに注意してください。

この問題に対して、下記のAC回答があります。

何故この回答はxとyに1e-14の誤差を足さないで、rだけに誤差を足しますか?

#include<bits/stdc++.h>
using namespace std;
long double x,y,r;
long long ans=0;
int main()
{
    cin>>x>>y>>r;
    r+=1e-14;
    for(long long i=ceil(x-r);i<=floor(x+r);i++)
    {
        long double t=sqrt(r*r-(i-x)*(i-x));
        ans+=(floor(y+t))-(ceil(y-t))+1;
    }
    cout<<ans;
    return 0;
}
0

1 件の回答 1

0

xとyは円の中心なので、それに1e-14を足すと、円全体の位置が右上の方向にずれてしまい、別の円になってしまいます。
一方、rは円の半径なので、1e-14を足すと、円全体が少しだけ大きくなります。計算の誤差による取りこぼしをなくすために、中心は変えずに円を少しだけ大きくしているのだと思います。


とは言え、円を大きくしたことにより本来答えではない点を求めてしまう可能性を、排除できるかどうかは、わかりません。

2
  • 分かりやすい説明いただきありがとうございました!
    – SSHuv
    2021年2月9日 1:45
  • 自分は1e-7から1e-15まで幾つかの値を試しました。結果といて、1e-14でしか通過できません。このepsの値はちょうどで、浮動小数点数誤差で正しい解答集から失った格子点は取り戻せる(そのためにepsを大きくする必要)一方、誤って解答集以外の格子点を含める可能性はない(そのためにepsを小さくする必要)ですね(X,Y,Rは高々小数第 4 位まで与えられるので)。
    – SSHuv
    2021年2月9日 1:52

この質問に回答するには、ログインする必要があります。

求めていた回答ではありませんか? のタグが付いた他の質問を参照する。