胰芰 发表于 2025-6-9 16:40:34

题解: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$)。
#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) x.begin(), x.end()
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);
    cin.tie(0), cout.tie(0);
    // cin >> _test_;
    init();
    while (_test_--) {
      clear();
      solve();
    }
    return 0;
}
来源:程序园用户自行投稿发布,如果侵权,请联系站长删除
免责声明:如果侵犯了您的权益,请联系站长,我们会及时删除侵权内容,谢谢合作!
页: [1]
查看完整版本: 题解:AT_abc389_d [ABC389D] Squares in Circle