AtCoder Beginner Contest 191 Problem D

help
1

For AtCoder Contest 191 Problem D, there’s such an AC answer.

#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;
}

Why the answer doesn’t add epsilon 1e-14 to x and y but only to r?

2 
        #include <bits/stdc++.h>
        using namespace std;
         
        int main(){
            long double X, Y, R;
            cin >> X >> Y >> R;
         
            X = abs(X) + abs(ceil(R));
            Y = abs(Y) + abs(ceil(R));
         
            long long answer = 0;
            for(long long x = ceil(X - R); x <= X + R; ++x){
                long double dx = abs(X - x);
                long double dy = sqrt(R * R - dx * dx);
                long long y1 = floor(Y + dy);
                long long y2 = ceil(Y - dy);
                answer += (y1 - y2 + 1);
            }
         
            cout << answer;
         
            return 0;
        }
1 Like
3

Thanks for another solution. But I still don’t understand why…

4

And this also works:

        #include <bits/stdc++.h>
        using namespace std;
         
        int main(){
            long double X, Y, R;
            cin >> X >> Y >> R;
         
            X = X + ceil(R);
            Y = Y + ceil(R);
         
            long long answer = 0;
            for(long long x = ceil(X - R); x <= X + R; ++x){
                long double dx = abs(X - x);
                long double dy = sqrt(R * R - dx * dx);
                long long y1 = floor(Y + dy);
                long long y2 = ceil(Y - dy);
                answer += (y1 - y2 + 1);
            }
         
            cout << answer;
         
            return 0;
        }
5

Found an answer:

This solves rounding problems because the rounding errors are smaller than 1e-14. On the other hand, there is no number so near to the desired result that adding 1e-14 would make a change.

Actually this is a common technique. On every comparation of values such EPS is added, so that values differing in less than EPS behave like equal values.

In other words, if any of x, y or r has rounding error so that a grid point is lost, adding 1e-14 to r will take back that point; if no grid point is lost (whether or not there are rounding errors), adding 1e-14 won’t mistakenly add more points (as the precision of x, y and r are so big as 1e-4).