螺旋折线
题目描述
如下图所示的螺旋折线经过平面上所有整点恰好一次。
对于整点 (X,Y)(X,Y)，我们定义它到原点的距离 dis(X,Y)dis(X,Y) 是从原点到 (X,Y)(X,Y) 的螺旋折线段的长度。
例如 dis(0,1)=3,dis(−2,−1)=9dis(0,1)=3,dis(−2,−1)=9。
给出整点坐标 (X,Y)(X,Y)，你能计算出 dis(X,Y)dis(X,Y) 吗？
输入描述
输入格式：
输入一行，XX 和 YY ，−109≤X,Y≤109−109≤X,Y≤109。
输出描述
输出 dis(X,Y)dis(X,Y)。
输入输出样例
示例
输入
0 1
输出
3
运行限制
- 最大运行时间：1s
- 最大运行内存: 256M
总通过次数: 1966 | 总提交次数: 2580 | 通过率: 76.2%
难度: 中等 标签: 2018, 思维, 省赛
方法思路
题目要求计算螺旋折线上任意点 (X, Y) 到原点的折线长度。螺旋折线从原点 (0,0) 开始，以逆时针方向向外螺旋扩展。通过观察螺旋折线的规律，我们可以将问题分解为以下步骤：
-
确定点所在的层数：螺旋折线可以看作由多个正方形环组成，每个环对应一个层数。点 (X, Y) 所在的层数
n是|X|和|Y|中的最大值，即n = max(|X|, |Y|)。 -
计算内层环的总长度：对于层数
n，所有内层环（即从第 0 层到第n-1层）的总长度是4 * n * n（因为每个环的周长递增，内层环的总长度公式推导为4n²）。 -
计算当前点在当前层的长度：
-
如果
X >= Y，则点在当前层中满足一定条件，长度增加|X - n| + |Y - n|。 -
如果
X < Y，则点在当前层中满足另一条件，长度减少|X - n| + |Y - n|。#include <iostream> #include <cmath> #include <algorithm> using namespace std; typedef long long LL;int main() {LL x, y;cin >> x >> y;LL n = max(abs(x), abs(y)); // 确定点所在的层数if (x >= y) {// 点在当前层中满足 X >= Ycout << 4 * n * n + abs(x - n) + abs(y - n) << endl;} else {// 点在当前层中满足 X < Ycout << 4 * n * n - abs(x - n) - abs(y - n) << endl;}return 0; }代码解释
-
输入处理：读取整数坐标
x和y。 -
确定层数：计算
n = max(|x|, |y|)，表示点(x, y)所在的螺旋层。 -
示例验证
-
输入 (0, 1)：
n = max(0, 1) = 1，0 < 1，所以输出4 * 1 * 1 - |0-1| - |1-1| = 4 - 1 - 0 = 3。 -
输入 (-2, -1)：
n = max(2, 1) = 2，-2 < -1，所以输出4 * 2 * 2 - | -2-2| - | -1-2| = 16 - 4 - 3 = 9。 -
输入 (1, 0)：
n = max(1, 0) = 1，1 >= 0，所以输出4 * 1 * 1 + |1-1| + |0-1| = 4 + 0 + 1 = 5。 -
计算距离：
-
内层环总长度：
4 * n * n表示所有内层环的折线总长度。 -
当前层偏移量：
-
如果
x >= y，点在当前层的偏移量是abs(x - n) + abs(y - n)，因此总长度为4 * n * n + abs(x - n) + abs(y - n)。 -
如果
x < y，点在当前层的偏移量是- (abs(x - n) + abs(y - n))，因此总长度为4 * n * n - abs(x - n) - abs(y - n)。
-
-
-
输出结果：根据上述条件计算并输出点
(x, y)到原点的螺旋折线长度。
-
