Open2021/02/21にコメント追加1

丸め処理とnextafter

C++

AtCoder

勉強ノート

log5

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

駄目だった回答

#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 というものを知った。

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

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

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

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