Solution: AT_abc389_d [ABC389D] Squares in Circle

Assume the origin is the center of the circle.

We only consider the case where the point is in the first quadrant, and the rest of the cases are the same.

Because the center of the circle is the origin, the abscissa coordinate of a point in the circle must be\(r\)within.

The abscissa of the enumeration point\(x + \frac{1}{2}\), the largest two points\(y + \frac{1}{2}\), making the point\((x + \frac{1}{2}, y + \frac{1}{2})\)distance to origin\(\le r\)(Because we let the center of the circle be the origin, all points should be translated by a certain distance).

At this time, all abscissas are\(x + \frac{1}{2}\)The points inside the circle are:

Totally\(y + 1\)indivual.

will enumerate all\(x\)The calculated answers are added up and recorded as\(t\)。

Since we only considered the first quadrant, the answer is\(4 \times t + 1\)(You need to consider the origin, so $ + 1$).

#include <bits/stdc++.h>
#define int long long
#define pii pair<int, int>
#define FRE(x) freopen(x ".in", "r", stdin), freopen(x ".out", "w", stdout)
#define ALL(x) (), ()
using namespace std;

inline void cmax(int& x, int c) {
    x = max(x, c);
}
inline void cmin(int& x, int c) {
    x = min(x, c);
}

int _test_ = 1;

int n, ans; 

double dis(double x, double y) {
    return (double)sqrt((double)((double)((double)x + 0.5) * (double)((double)x + 0.5) + (double)((double)y + 0.5) * (double)((double)y + 0.5)));
}

void init() {}

void clear() {}

void solve() {
    cin >> n;
    for (int i = 1; i < n; i++) {
        int l = 0, r = n, t = 0;
        while (l <= r) {
            int mid = (l + r) >> 1;
            if (dis(i, mid) <= (double)n) {
                t = mid;
                l = mid + 1;
            } else
                r = mid - 1;
        }
        ans += t + 1;
    }
    cout << ans * 4 + 1;
}

signed main() {
    ios::sync_with_stdio(0);
    (0), (0);
    // cin >> _test_;
    init();
    while (_test_--) {
        clear();
        solve();
    }
    return 0;
}