Open1

丸め処理とnextafter

ABC191 の D問題が解けずにめちゃくちゃハマった。

https://atcoder.jp/contests/abc191/tasks/abc191_d

駄目だった回答

https://atcoder.jp/contests/abc191/submissions/20015165
#include <bits/stdc++.h>

using namespace std;
using ll = long long;

int main() {
    long double X, Y, R;
    cin >> X >> Y >> R;

    ll left, right;
    ll answer = 0;

    left = ceil(X - R);
    right = floor(X + R);
    for (ll i = left; i <= right; ++i) {
        long double height = sqrt(pow(R, 2) - pow((X - i), 2));
        answer += floor(Y + height) - ceil(Y - height) + 1;
    }
    cout << answer << endl;
}

どうしても2ケースだけ通らない...

色々3時間くらい試行錯誤の結果、nextafter というものを知った。

http://www.c-tipsref.com/reference/math/nextafter.html
次に表現可能な値を予め知っておけば、変な丸め処理とかが割り込んで事故ることが減る...かもしれない的な理解しかできなかったけど、なんとなく見様見真似で使ってみたらACできた。

最終的にこんな感じに落ち着いた。

https://atcoder.jp/contests/abc191/submissions/20016684
#include <bits/stdc++.h>

using namespace std;
using ll = long long int;

int main() {
    long double X, Y, R;
    cin >> X >> Y >> R;
    ll answer = 0;

    R = nextafter(R, INFINITY);

    for (ll i = ceil(X - R); i <= floor(X + R); ++i) {
        long double height = sqrt(pow(R, 2) - pow((i - X), 2));
        answer += floor(Y + height) - ceil(Y - height) + 1;
    }

    cout << answer << endl;
}

浮動小数点数の処理は大変ですね

ログインするとコメントできます