[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;
}
この記事が気に入ったらサポートをしてみませんか?