螺旋折线（18年第七题）

Dear 丶 2022-03-09 01:08 228阅读 0赞

## 第七题 标题：螺旋折线（18年第七题） ##

如图 所示的螺旋折线经过平面上所有整点恰好一次。  
对于整点(X, Y)，我们定义它到原点的距离dis(X, Y)是从原点到(X, Y)的螺旋折线段的长度。  
例如dis(0, 1)=3, dis(-2, -1)=9  
给出整点坐标(X, Y)，你能计算出dis(X, Y)吗？  
![p1.png][]  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxNzA5ODAx_size_16_color_FFFFFF_t_70]

定义数值：  
设当前所在螺旋层数为 **C** 层。  
第一步：分析出特殊的有规律的点。  
右上顶点: 值为 \*\*(C \* 2)^2 \*\* 设为 **M**  
左下顶点: 值为 \*\*(c \* 2 - 1) ^2 \*\* 设为 **N**  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxNzA5ODAx_size_16_color_FFFFFF_t_70 1]  
由特殊点制造有用点，方便解题。  
将象限交界点用 **M, N, C** 表示，然后对螺旋经行分割。（按象限经行分割）。  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxNzA5ODAx_size_16_color_FFFFFF_t_70 2]  
下一步就是推算点的计算公式。由于对象限经行分割，那么每个象限都可以取不同的参考点。  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxNzA5ODAx_size_16_color_FFFFFF_t_70 3]  
第三象限为两层螺旋交接处，要经行分段处理。  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxNzA5ODAx_size_16_color_FFFFFF_t_70 4]

以下便是测试代码，对于题目中的100%数据范围最大10亿也可以通过。  
如果不清楚，可以复制代码运行查看结果，然后再模拟画一下螺旋图，想必便知道解法了。

#include<stdio.h>
    #include<math.h>
    #include<stdlib.h>
    #define Max(a, b) ((a) > (b) ? (a) : (b)) 
    typedef long long ll;
    
    // 划分象限 
    int dir(ll x, ll y){ 
    	if(x >= 0){ 
    		if(y >= 0){ 
    			return 1; 
    		} else { 
    			return 4;
    		} 
    	}else{ 
    		if(y >= 0){ 
    			return 2;
    		}else{ 
    			return 3;
    		}
    	}
    }
    ll get(ll x, ll y){ 
    // 这里用位运算代替许多乘法可以提高速度。
    // 10 >> 1 = 5 (>>1相当于除2)
    // 10 << 1 = 20 (<<1相当于乘2)
    	printf("输入坐标: (%lld, %lld)\n", x, y);
    	ll ceng = Max(abs(x), abs(y));
    	printf("坐标所在螺旋层数: %lld\n", ceng); 
     
    	// (2*x)^2 
    	ll n = ((ceng << 1) - 1) * ((ceng << 1) - 1); 
    	
    	ll m = ((ceng << 1) * (ceng << 1)); 
    	
    	printf("所在螺旋层数左下角顶点: %lld\n", n); 
     	printf("所在螺旋层数右上角顶点: %lld\n", m); 
     	
    	ll re = 0;
    	switch(dir(x, y)){ // 处理各个象限
    		case 1:
    			printf("1象限: 1象限与2象限交点: %lld\n", m - ceng);
     			re = (m - ceng) + ((ceng) - (y - x));
    			break;
    		case 2:
    			printf("2象限: 2象限与3象限交点: %lld\n", n + ceng -1);
     			re = (n + ceng - 1) + (ceng + (x + y));
    			break;
    		case 3: 
     			if(y <= x){ // 分段处理
     				printf("3象限: 3象限与4象限交点: %lld\n", m + (ceng << 1) + ceng);
     				re = (m + (ceng << 1) + ceng) +  (- x);
    			}else{ 
    				printf("3象限: 3象限与4象限交点: %lld\n", n + ceng - 1);
     				re = (n + ceng - 1) + (y);
    			}
    			break;
    		case 4:
    			printf("4象限: 1象限与4象限交点: %lld\n", m + ceng);
     			re = (m + ceng) + (ceng - x - y);
    			break;		
    	}
    }
    int main(){ 
    	
    	ll x = 1000000000;
    	ll y = -1000000000;
    
    	ll result = get(x, y);
    	printf("结果: %lld\n", result);
    	
    	return 0;
    }

[p1.png]: /images/20220309/5c5efa6ab58d43c4ac6aace46f20b4ed.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxNzA5ODAx_size_16_color_FFFFFF_t_70]: /images/20220309/1893150b5f0a497496f0c622be36dd3c.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxNzA5ODAx_size_16_color_FFFFFF_t_70 1]: /images/20220309/9f0df21c179e410083f92cca50663068.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxNzA5ODAx_size_16_color_FFFFFF_t_70 2]: /images/20220309/5dda1379f3784cbf8bdddde48721c5f5.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxNzA5ODAx_size_16_color_FFFFFF_t_70 3]: /images/20220309/aea6c2eb6ae54036b00ef4129c853582.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxNzA5ODAx_size_16_color_FFFFFF_t_70 4]: /images/20220309/4d0960f927484ee6b8fa4e810b60111c.png