正方形の中心が格子点となるように座標を取り、円の中心を \((0,0)\) とします。

条件を満たす \((i,j)\) のうち、\(i=0\) または \(j=0\) を満たすものの個数は簡単に分かり、原点かそうでないかで場合分けをすると \(4(R-1)+1\) 個です。

次に \(i\neq 0\) かつ \(j\neq 0\) を満たすものの個数を求めましょう。対称性より \(i>0\) かつ \(j>0\) を満たすものの個数を求め最後に \(4\) 倍すればよいです。

\(i\) を \(1,2,\ldots,R-1\) の順に全探索しましょう。このとき、\((i+0.5)^2+(j+0.5)^2\leq R^2\) を満たす整数 \(j\) の最大値は単調に減少します。

このことから、\(j\) の最大値を尺取り法で管理することで、時間計算量 \(\mathrm{O}(R)\) の解法が得られます。尺取り法の実装の詳細については実装例も参考にしてください。

また、本問題では小数を用いて計算しても問題ありませんが、一般には誤差の影響がありうるため、整数のみで計算できる場合はそのように変形した方が良い場合も多いです。

例えば本問題では、 \((i+0.5)^2+(j+0.5)^2\leq R^2\) の両辺を \(4\) 倍して \((2i+1)^2+(2j+1)^2\leq 4R^2\) と同値変形することで、全ての計算を整数で行うことができます。

実装例(C++):

#include <bits/stdc++.h>
using namespace std;
using ll = long long;

int main() {
    ll r;
    cin >> r;
    auto in = [&](ll a, ll b) {
        return (2 * a + 1) * (2 * a + 1) + (2 * b + 1) * (2 * b + 1) <= 4 * r * r;
    };
    ll cnt = 0;
    ll up = r - 1;
    ll res = (r - 1) * 4 + 1;
    for(ll x = 1; in(x, 1); x++) {
        while(!in(x, up)) --up;
        cnt += up;
    }
    res += cnt * 4;
    cout << res << endl;
}