算法
(几何) $O(R\log R)$
枚举纵坐标,再根据勾股定理求出横坐标的合法范围,并判断该范围内有多少格点。
值得注意的是这题比较卡精度,所以需要一些特殊处理。
C++ 代码
#include <bits/stdc++.h>
using std::cin;
using std::cout;
using ll = long long;
int in() {
double x;
cin >> x;
x *= 10000;
return round(x);
}
bool ok(ll dx, ll dy, ll z) {
return dx * dx + dy * dy <= z * z;
}
ll f(ll x, ll y, ll z, ll lim) {
int l = 0, r = 1;
ll res = 0;
for (int i = (int)1e9 + 50000; i >= lim; i -= 10000) {
while (ok(x - l * 10000, i - y, z)) --l;
while (ok(r * 10000 - x, i - y, z)) ++r;
res += r - l - 1;
}
return res;
}
int main() {
ll x = in();
ll y = in();
ll r = in();
x %= 10000;
y %= 10000;
ll ans = f(x, y, r, 10000);
ans += f(x, -y, r, 0);
cout << ans << '\n';
return 0;
}