73877


下記[AtCoder Contest
191のD問題](https://atcoder.jp/contests/abc191/tasks/abc191_d)について質問させていただきたいです。

> **問題文**
>
> 2次元平面上に中心 (X,Y) 、半径 R の円があります。 この円の内部または周上にある格子点 (x,y座標がともに整数である点)  
>  の個数を求めてください。
>
> **制約**
>
>   * |X|≤105
>   * |Y|≤105
>   * 0<R≤105
>   * X,Y,Rは高々小数第 4 位まで与えられる
>

>
> **入力**
>
> 入力は以下の形式で標準入力から与えられる。
[code]

>     X Y R
>  
[/code]

>
> **入力例 1**
[code]

>     0.2 0.8 1.1
>  
[/code]

>
> **出力例 1**
[code]

>     3
>  
[/code]

>
> 以下のような円になります。赤く印の付いた点が、この円の内部または周上にある格子点です。  
>
> [![](https://i.stack.imgur.com/Utulf.png)](https://i.stack.imgur.com/Utulf.png)
>
> **入力例 2**
[code]

>     100 100 1
>  
[/code]

>
> **出力例 2**
[code]

>     5
>  
[/code]

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

この問題に対して、[下記のAC回答](https://atcoder.jp/contests/abc191/submissions/20023044)があります。

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

[code]

    #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;
    }
    
[/code]


CC BY-SA 4.0
2021-02-08T04:48:45.137
73854
2021-02-09T01:41:42.207
2021-02-09T01:41:42.207
43877
43877
question
c++ 浮動小数点数
AtCoder ABC190Dの回答に何故Rだけ誤差対応するか


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

* * *

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


CC BY-SA 4.0
2021-02-09T00:30:49.323
73877
2021-02-09T00:30:49.323
3605
73854
answer