[蓝桥杯 2018 省 B] 螺旋折线
题目描述
如图所示的螺旋折线经过平面上所有整点恰好一次。
对于整点 (X,Y)，我们定义它到原点的距离 dis(X,Y) 是从原点到(X,Y) 的螺旋折线段的长度。
例如 dis(0,1)=3，dis(−2,−1)=9。
给出整点坐标 (X,Y)，你能计算出 dis(X,Y) 吗？
输入格式
X 和 Y。
输出格式
输出dis(X,Y)
输入输出样例
输入 #1 0 1
输出 #1 3
说明/提示
对于 40%的数据，−−1000≤X,Y≤1000。
对于 70% 的数据，− 
≤X,Y≤ 
。
对于 100% 的数据，− 
≤X,Y≤ 
。
思路
对于这个题，我把图中所有的点都列了出来然后发现规律
（0，0） 0
对于绝对值最大是1的
（-1，0） 1
（-1，1） 2
（0，1） 3
（1，1） 4
（1，0） 5
（1，-1） 6
（0，-1） 7
（-1，-1） 8
对于绝对值最大是2的
（-2，-1) 9
（-2，0) 10
（-2，1) 11
（-2，2) 12
(-1，2） 13
(0，2） 14
(1，2） 15
(2，2） 16
（2，1） 17
（2，0） 18
（2，-1） 19
（2，-2） 20
（1，-2） 21
（0，-2） 22
（-1，-2） 23
（-2，-2） 24
对于绝对值最大是3的
（-3，-2） 25
（-3，-1） 26
（-3，0） 27
（-3，1） 28
（-3，2） 29
（-3，3） 30
（-3，3） 31
（-2，3） 32
（-1，3） 33
（0，3） 34
（1，3） 35
（2，3） 36
（3，2) 37
（3，1) 38
（3，0) 39
（3，-1) 40
（3，-2) 41
（3，-3) 42
（2，-3) 43
（1，-3) 44
（0，-3） 45
（-1，-3） 46
（-2，-3） 47
（-3，-3） 48
假设最大的绝对值为n,可以发现每一种距离的范围都是 
到 
(不包括 
）因此可以根据n来缩小计算的范围
代码1
#include<iostream> #include<cmath>//包含求绝对的函数 using namespace std; int main() { long long int x,y,num=0,a; cin>>x>>y; long long int n=(abs(x)>abs(y))?abs(x):abs(y); long long int X=(-1)*n,Y=(-1)*(n-1);//第一个坐标 for(long long int i=(2*n-1)*(2*n-1)+1;i<(2*n+1)*(2*n+1);i++) { if(X == ( - 1 ) * n && Y > (-1)*n && Y < n ) Y ++; else if ( X < n && X >= ( - 1 ) * n && Y == n)X++; else if(X == n && Y <= n && Y > ( - 1 ) * n)Y--; else if(X < n && X > ( - 1 ) * n && Y == ( - 1 ) * n) X--; else; if(Y==y&&X==x) { num=i; break; } } cout<<num<<endl; return 0; }
这样对于大的数字就会超时，只能得84分
后面我又根据横坐标和做坐标相同，可以将每个分为4部分，每次找到这一部分的第一个在开始遍历，就又缩小计算的范围，缩短时间。
代码2
#include<iostream> #include<cmath>//包含求绝对的函数 using namespace std; int main() { long long int x,y,num=0,a; cin>>x>>y; long long int n=(abs(x)>abs(y))?abs(x):abs(y); long long int X=0,Y=0; if(x==(-1)*n){a=0;X=(-1)*n,Y=(-1)*(n-1);} if(y==n){a=1;Y=n,X=(-1)*(n-1);} if(x==n){a=2;X=n,Y=n-1;} if(y==(-1)*n){a=3;X=n-1,Y=(-1)*n;} //a代表第几部分 long long int b=(2*n-1)*(2*n-1)+a*2*n; for(long long int i=b;i<b+2*n;i++) { if(Y==y&&X==x) { num=i; break; } if(X == ( - 1 ) * n && Y > (-1)*n && Y < n ) Y++; else if ( X < n && X >= ( - 1 ) * n && Y == n)X++; else if(X == n && Y <= n && Y > ( - 1 ) * n)Y--; else if(X <= n && X > ( - 1 ) * n && Y == ( - 1 ) * n) X--; else; } cout<<num<<endl; return 0; }
最后吧这个放在一起方便观察
