题解：AT_abc389_d [ABC389D] Squares in Circle

假定原点为圆心。
我们只考虑点在第一象限的情况，剩下的情况同理。
因为圆心是原点，所以在圆内的点的横坐标一定在 \(r\) 之内。
枚举点的横坐标 \(x + \frac{1}{2}\)，二分最大的 \(y + \frac{1}{2}\)，使得点 \((x + \frac{1}{2}, y + \frac{1}{2})\) 到原点的距离 \(\le r\) （因为我们令圆心为原点，所以所有的点都应平移一段）。
此时所有横坐标为 \(x + \frac{1}{2}\) 的在圆内的点分别是：

\[(x + \frac{1}{2}, \frac{1}{2}),(x + \frac{1}{2}, 1 + \frac{1}{2}),(x + \frac{1}{2}, 2 + \frac{1}{2}),\dots,(x + \frac{1}{2}, y + \frac{1}{2})\]
一共是 \(y + 1\) 个。
将枚举的所有 \(x\) 算出来的答案加起来记为 \(t\)。
因为我们只考虑了第一象限，所以答案是 \(4 \times t + 1\)（需要考虑原点的情况，所以要 $ + 1$）。

1. #include <bits/stdc++.h>
2. #define int long long
3. #define pii pair<int, int>
4. #define FRE(x) freopen(x ".in", "r", stdin), freopen(x ".out", "w", stdout)
5. #define ALL(x) x.begin(), x.end()
6. using namespace std;
8. inline void cmax(int& x, int c) {
9.     x = max(x, c);
10. }
11. inline void cmin(int& x, int c) {
12.     x = min(x, c);
13. }
15. int _test_ = 1;
17. int n, ans;
19. double dis(double x, double y) {
20.     return (double)sqrt((double)((double)((double)x + 0.5) * (double)((double)x + 0.5) + (double)((double)y + 0.5) * (double)((double)y + 0.5)));
21. }
23. void init() {}
25. void clear() {}
27. void solve() {
28.     cin >> n;
29.     for (int i = 1; i < n; i++) {
30.         int l = 0, r = n, t = 0;
31.         while (l <= r) {
32.             int mid = (l + r) >> 1;
33.             if (dis(i, mid) <= (double)n) {
34.                 t = mid;
35.                 l = mid + 1;
36.             } else
37.                 r = mid - 1;
38.         }
39.         ans += t + 1;
40.     }
41.     cout << ans * 4 + 1;
42. }
44. signed main() {
45.     ios::sync_with_stdio(0);
46.     cin.tie(0), cout.tie(0);
47.     // cin >> _test_;
48.     init();
49.     while (_test_--) {
50.         clear();
51.         solve();
52.     }
53.     return 0;
54. }

复制代码

来源：程序园用户自行投稿发布，如果侵权，请联系站长删除
免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！