蓝桥杯刷题|04普及-真题

[蓝桥杯 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% 的数据，− $10^{5}$ ≤X,Y≤ $10^{5}$ 。

对于 100% 的数据，− $10^{9}$ ≤X,Y≤ $10^{9}$ 。

思路

对于这个题，我把图中所有的点都列了出来然后发现规律

（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,可以发现每一种距离的范围都是 $(2n-1)^{2}$ 到 $(2n+1)^{2}$ (不包括 $(2n+1)^{2}$ ）因此可以根据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;
}