題目大意
科學(xué)家目前正在開發(fā)一種稱為“方形螺旋搜索”的算法。該算法按以下順序搜索存儲(chǔ)器位置（也在圖中示出）：
現(xiàn)在他想知道：使用方形螺旋搜索到達(dá)地址（x毁渗，y）的內(nèi)存位置需要多少步璃弄。
圖中藍(lán)色數(shù)字為所走步數(shù)肝断。
這題其實(shí)是一個(gè)江恩螺旋四方形迂尝，這個(gè)四方形有個(gè)套路：
- 右下對(duì)角線上的數(shù)字是 1鞠评、9茂蚓、25、49剃幌、81聋涨、121、169负乡、225......分別是1牍白、3、5抖棘、7茂腥、9、11切省、13.....這些單數(shù)的平方最岗。
res = (2st+1)(2*st+1)-1（st為其所在圈數(shù)）
而在本題中其右下方分別是1、3朝捆、5般渡、7、9芙盘、11驯用、13.....這些單數(shù)的平方-1。
- 左上對(duì)角線上的數(shù)字減1是 4何陆、16晨汹、36、64贷盲、100淘这、144剥扣、169......分別是2、4铝穷、6钠怯、8、10曙聂、12晦炊、14.....這些雙數(shù)的平方。
res = (st×2)*(st×2) = 4 ×st
于是筆者把它分類討論了一下宁脊，
斜線右上方的取第二圈最大值點(diǎn)16（-2断国， 2） ，第一圈最大值點(diǎn)4（-1榆苞，1 ）
斜線左下方的取第二圈最大值點(diǎn)24（2稳衬，-2），第一圈最大值點(diǎn)8（-1坐漏，1）
屬于右上分塊同一圈的其余點(diǎn)的步數(shù)就等于薄疚，該圈最大步數(shù)減去所求點(diǎn)（x1, y1）到最大步數(shù)點(diǎn)的距離。
然后兩個(gè)分塊的處理上有些細(xì)節(jié)
輸入分析
3
1 0//此點(diǎn)屬于右下-第一圈赊琳，步數(shù)最大值點(diǎn)4（-1街夭，1），△x = |（-1）-1|=2躏筏，△y=|1-0|=1板丽，此點(diǎn)步數(shù)=4-△x-△y=1
1 1
-2 1//此點(diǎn)屬于左下-第二圈，步數(shù)最大值點(diǎn)24（2寸士， -2）檐什，△x= |（-2）-2|=4碴卧，△y=|-2-1|=3弱卡，此點(diǎn)步數(shù)=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中大的數(shù)字確認(rèn)該點(diǎn)位于第st圈
if (x + y == 0) //該點(diǎn)在線上
{
if (x >= 0) res = (2*st+1)*(2*st+1)-1;//屬于左下段
else res = (2*st)*(st*2);//屬于右上段
}
else if (x+y > 0) //該點(diǎn)位于斜線右上方
{
res = (2*st)*(st*2);//該圈中步數(shù)的最大值
res = res - abs(x+st) - abs(st-y); //求出該點(diǎn)位置
}
else
{
res = (2*st+1)*(2*st+1)-1;
res = res - abs(x-st) - abs(st+y);
}
printf("%lld\n", res);
}
return 0;
}
ps
這題數(shù)據(jù)范圍
-?1,?000,?000,?000?≤?X?≤?1,?000,?000,?000
-?1,?000,?000,?000?≤?Y?≤?1,?000,?000,?000
不能用int 要用long long
