[ABC191] D - Circle Lattice Points

[Q] https://atcoder.jp/contests/abc191/tasks/abc191_d

1. yを固定して、ありうるxの幅を求めようと思う。
y=0のとき、xの左端とxの右端をにぶたんで求める。
y=1のとき、xの左端とxの右端をにぶたんで求める。
...
2. (y, x)が円に含まれているかどうかは、円の中心からの距離がRを超えるかどうか、で判定できそう。
3. (-200000, 0) から (200000, 0)まで円に入りうるので、yは-200000から200000まで走査する。

Q. 1WAが抜けない？？？

0.999 0 0.001

このパターンが永遠に沼だった。
1WAを潰したら8WAが生えて、8WAを潰したら2WAが生えて、2WAを潰したら6WAが生えた。どうやらdoubleの誤差が肝のよう。
誤差解説がとても詳しい
https://sen-comp.hatenablog.com/entry/2021/02/18/164536

4. doubleの上5桁 + 下4桁 = 9桁まで入るし、それを三平方で2剰するので、18桁まで数値を扱いうる。
だけど、doubleは15-16桁までしか正確にとれない。
自分が死んでいたのはこの判定。

// 右端を探す。
ll binary_search_R(ll &y, ll l, ll r) {
 if (dist(X, l, Y, y) > R) return l - 1; // もし左端すら含まれないなら、左端-1を返す

デバッグをすると

dist() = 0.001
dist() > 0.001 // true

0.001と0.001の比較なのに、なぜかdistの0.001がちょっと大きい。
Rを補正する。

 R += 0.00000000000000001;

この補正は1e-14未満でないとWAを食らう。

実装

ld dist(ld x1, ld x2, ld y1, ld y2) {
 return (sqrtl((x2 - x1) * (x2 - x1) + (y2 - y1) * (y2 - y1)));
}

ld X, Y, R;
ll binary_search_L(ll &y, ll l, ll r) {
 if (dist(X, r, Y, y) > R) return r + 1;
 while (r - l > 1) {
   ll mid = (l + r) / 2;
   //(y, mid)が範囲内かどうか
   if (dist(X, mid, Y, y) <= R) {
     r = mid;
   } else
     l = mid;
 }
 return r;
}

ll binary_search_R(ll &y, ll l, ll r) {
 if (dist(X, l, Y, y) > R) return l - 1;
 while (r - l > 1) {
   ll mid = (l + r) / 2;
   //(y, mid)が範囲内かどうか
   if (dist(X, mid, Y, y) <= R) {
     l = mid;
   } else
     r = mid;
 }
 return l;
}

int main() {
 cincout();

 cin >> X >> Y >> R;
 R += 0.00000000000000001; // 補正
 ll ans = 0;
 for (ll y = -200000; y <= 200000; ++y) {
   ll lx = binary_search_L(y, -200005, X);
   ll rx = binary_search_R(y, X + 1, 200005);
   ans += max(rx - lx + 1, 0LL);
 }
 cout << ans << endl;
}