F. Circle Perimeter - 题解
比赛与标签
比赛: Codeforces Round 944 (Div. 4) 标签: binary search, brute force, dfs and similar, geometry, implementation, math 难度: *1600
题目大意喵~
主人你好呀~！这道题是想让我们当一回小小数学家呢，喵！
题目会给我们一个整数半径 r，然后需要我们找出所有坐标是整数的点 (x, y)（也就是格点），这些点到原点 (0, 0) 的距离 d 必须满足 r <= d < r+1。最后，我们要数一数一共有多少个这样的点，的说。
简单来说，就是在坐标系上画两个同心圆，一个半径是 r，另一个半径是 r+1。我们要找的就是落在这两个圆之间（包括内圈，但不包括外圈）的整数坐标点有多少个，呐。
用数学语言来描述，就是找到满足下面这个不等式的整数对 (x, y) 的数量： r <= sqrt(x^2 + y^2) < r+1
解题思路，一起攻克它！
看到 sqrt (开方) 是不是有点头大呀？没关系，猫娘有办法让它变简单！
第一步：甩掉烦人的根号！
不等式两边都是正数，我们可以对整个不等式进行平方，这样既能去掉根号，又不会改变大小关系，计算起来也更精确，喵~ r^2 <= x^2 + y^2 < (r+1)^2 看，这样是不是清爽多啦？我们的问题就变成了：寻找有多少对整数 (x, y) 满足这个关于平方和的不等式。
第二步：对称大法好！
观察一下 x^2 + y^2 这个式子，是不是超级对称？如果 (x, y) 是一个解，那么 (-x, y), (x, -y), (-x, -y) 肯定也满足条件！而且，如果 x 和 y 不相等，那么 (y, x) 也是一个解。
利用这个完美的对称性，我们可以大大简化问题！我们只用数出第一象限（x > 0, y > 0）里有多少个点，然后把结果乘以 4。最后再单独处理坐标轴上的点就大功告成啦！
第三步：坐标轴上的点点~
先来处理最简单的部分——坐标轴上的点。
- 当
x = 0时，不等式变为r^2 <= y^2 < (r+1)^2。因为y是整数，所以|y|只能等于r。这样我们就找到了两个点：(0, r)和(0, -r)。 - 当
y = 0时，同理，x只能是r或-r。这样又找到了两个点：(r, 0)和(-r, 0)。
所以，在坐标轴上，我们稳稳地拿到了 4 个点，喵！
第四步：第一象限的双指针魔法！
现在是核心部分啦！我们要计算在 x > 0, y > 0 的范围内有多少个满足条件的点。
我们可以固定 x，然后去找合法的 y 有多少个。x 的取值范围是什么呢？因为 x^2 + y^2 >= r^2 且 y > 0，所以 x 最大不会超过 r（如果 x > r，x^2 就已经大于 r^2 了）。所以，我们只需要遍历 x 从 1 到 r 就可以了。
对于每一个固定的 x，我们需要找到有多少个正整数 y 满足： r^2 - x^2 <= y^2 < (r+1)^2 - x^2
一个一个 y 去试太慢啦！这里有一个超级厉害的技巧——双指针！
- 我们定义
y_outer，表示对于当前的x，满足x^2 + y^2 < (r+1)^2的最大正整数y。 - 我们定义
y_inner，表示对于当前的x，满足x^2 + y^2 < r^2的最大正整数y。
那么，对于这个 x，所有合法的 y 的数量就是 y_outer - y_inner！
最神奇的地方来啦：当我们把 x 从 1 慢慢增加到 r 时，y_outer 和 y_inner 的值是不会增加的，只会保持不变或者减小。所以，我们根本不需要为每个 x 都重新计算 y 的范围。我们可以初始化 y_outer 和 y_inner (例如对于 x=1 的情况)，然后在 x 增加的循环里，不断地让 y_outer 和 y_inner “向下滑动”到正确的位置。这个方法是不是很优雅，喵~
第五步：汇总答案！
最后，我们把所有部分加起来： 总点数 = 坐标轴上的点数 + 4 * (第一象限的点数)总点数 = 4 + 4 * quadrant_points
这样，我们就高效地解决了问题啦！
代码实现喵~
#include <iostream>
void solve() {
long long r;
std::cin >> r;
// 我们需要找到整数点 (x, y) 满足
// r <= sqrt(x^2 + y^2) < r + 1
// 两边平方得到: r^2 <= x^2 + y^2 < (r+1)^2
// 使用 long long 防止 r*r 溢出，因为 r 最大是 10^5
long long r_sq = r * r;
long long r_plus_1_sq = (r + 1) * (r + 1);
// quadrant_points 用于统计第一象限 (x > 0, y > 0) 的点数
long long quadrant_points = 0;
// 这里使用双指针技巧来优化计算
// 当 x 增加时, 满足条件的 y 的上界只会减小或不变
// y_outer: 对于当前 x, 满足 x^2 + y^2 < (r+1)^2 的最大 y
long long y_outer = r;
// y_inner: 对于当前 x, 满足 x^2 + y^2 < r^2 的最大 y
long long y_inner = r - 1;
// 遍历第一象限的 x 轴，x 的范围是 [1, r]
for (long long x = 1; x <= r; ++x) {
long long x_sq = x * x;
// 向下调整 y_outer 指针
// 找到第一个使得 x^2 + y_outer^2 < (r+1)^2 的 y_outer
while (y_outer > 0 && x_sq + y_outer * y_outer >= r_plus_1_sq) {
y_outer--;
}
// 向下调整 y_inner 指针
// 找到第一个使得 x^2 + y_inner^2 < r^2 的 y_inner
while (y_inner > 0 && x_sq + y_inner * y_inner >= r_sq) {
y_inner--;
}
// 对于当前的 x, 合法的 y 的数量就是 y_outer - y_inner
quadrant_points += (y_outer - y_inner);
}
// 总点数 = 坐标轴上的4个点 + 4 * 第一象限的点数
// 坐标轴上的点是 (r, 0), (-r, 0), (0, r), (0, -r)
long long total_points = 4 + 4 * quadrant_points;
std::cout << total_points << std::endl;
}
int main() {
// 加速输入输出，喵~
std::ios_base::sync_with_stdio(false);
std::cin.tie(NULL);
int t;
std::cin >> t;
while (t--) {
solve();
}
return 0;
}复杂度分析
时间复杂度: O(r) 的说。 主循环从
x=1遍历到r，看起来是O(r)。循环内部的两个while循环呢？虽然它们看起来像嵌套循环，但指针y_outer和y_inner在整个for循环的生命周期里，都只会单调递减。y_outer总共最多从r减到0，y_inner也是。所以while循环的总执行次数是O(r)级别的。因此，总的时间复杂度是O(r)。考虑到所有测试用例的r之和不超过10^5，这个速度是飞快的！空间复杂度: O(1) 的说。 我们只用了几个变量来存储半径、坐标和计数值，没有用到随
r增大的额外空间，所以空间复杂度是常数级别，非常优秀，喵~！
知识点与总结
这道题真是一次有趣的几何与算法结合之旅呀！
- 问题转化: 核心思想是把一个几何问题（点到原点的距离）转化为代数不等式
r^2 <= x^2 + y^2 < (r+1)^2，这让我们能够完全在整数域内进行精确计算。 - 对称性利用: 看到
x^2,y^2这种形式，就要立刻想到对称性！将问题分解到第一象限处理，再乘以4加上坐标轴上的点，是解决这类问题的经典思路。 - 双指针/尺取法: 这道题最亮眼的技巧就是双指针！它巧妙地利用了
y随x增大而单调不增的特性，将内层查找的复杂度从O(log r)(二分) 或O(r)(暴力) 优化到了均摊O(1)，使得整体复杂度达到线性的O(r)。 - 编程细节: 一定要注意使用
long long来防止r*r这样的计算导致整数溢出哦！
希望这篇题解能帮到你，主人！以后遇到类似的题目，也要记得从这几个角度去思考哦！继续加油，你超棒的，喵~！