题目大意
科学家目前正在开发一种称为“方形螺旋搜索”的算法。该算法按以下顺序搜索存储器位置（也在图中示出）：
现在他想知道：使用方形螺旋搜索到达地址（x，y）的内存位置需要多少步。
图中蓝色数字为所走步数。
这题其实是一个江恩螺旋四方形，这个四方形有个套路：
- 右下对角线上的数字是 1、9、25、49、81、121、169、225......分别是1、3、5、7、9、11、13.....这些单数的平方。
res = (2st+1)(2*st+1)-1（st为其所在圈数）
而在本题中其右下方分别是1、3、5、7、9、11、13.....这些单数的平方-1。
- 左上对角线上的数字减1是 4、16、36、64、100、144、169......分别是2、4、6、8、10、12、14.....这些双数的平方。
res = (st×2)*(st×2) = 4 ×st
于是笔者把它分类讨论了一下，
斜线右上方的取第二圈最大值点16（-2， 2） ，第一圈最大值点4（-1，1 ）
斜线左下方的取第二圈最大值点24（2，-2），第一圈最大值点8（-1，1）
属于右上分块同一圈的其余点的步数就等于，该圈最大步数减去所求点（x1, y1）到最大步数点的距离。
然后两个分块的处理上有些细节
输入分析
3
1 0//此点属于右下-第一圈，步数最大值点4（-1，1），△x = |（-1）-1|=2，△y=|1-0|=1，此点步数=4-△x-△y=1
1 1
-2 1//此点属于左下-第二圈，步数最大值点24（2， -2），△x= |（-2）-2|=4，△y=|-2-1|=3，此点步数=24-△x-△y=17
代码分析
#include <stdio.h>
#include <stdlib.h>
int main()
{
int t;
long long x, y, st, xx, yy, res;
scanf("%d", &t);
while(t--)
{
scanf("%lld%lld", &x, &y);
xx = abs(0-x);
yy = abs(0-y);
st = max(xx, yy); //选出x,y中大的数字确认该点位于第st圈
if (x + y == 0) //该点在线上
{
if (x >= 0) res = (2*st+1)*(2*st+1)-1;//属于左下段
else res = (2*st)*(st*2);//属于右上段
}
else if (x+y > 0) //该点位于斜线右上方
{
res = (2*st)*(st*2);//该圈中步数的最大值
res = res - abs(x+st) - abs(st-y); //求出该点位置
}
else
{
res = (2*st+1)*(2*st+1)-1;
res = res - abs(x-st) - abs(st+y);
}
printf("%lld\n", res);
}
return 0;
}
ps
这题数据范围
- 1, 000, 000, 000 ≤ X ≤ 1, 000, 000, 000
- 1, 000, 000, 000 ≤ Y ≤ 1, 000, 000, 000
不能用int 要用long long
