2018年蓝桥杯C/C++ B组省赛试题G：螺旋折线题解

灰太狼 2022-12-28 14:18 141阅读 0赞

### 文章目录 ###

*  题目描述
 *   *  输入格式
     *  输出格式
     *  样例输入
     *  样例输出
     *  资源约定：
 *  解题思路
 *  解题代码

--------------------

# 题目描述 #

如图所示的螺旋折线经过平面上所有整点恰好一次。

![题目描述][05X4p9.png]

对于整点(X, Y)，我们定义它到原点的距离dis(X, Y)是从原点到(X, Y)的螺旋折线段的长度。

例如`dis(0, 1)=3`, `dis(-2, -1)=9`

给出整点坐标(X, Y)，你能计算出dis(X, Y)吗？

## 输入格式 ##

> X和Y
> 
> 对于40%的数据，-1000 <= X, Y <= 1000
> 
> 对于70%的数据，-100000 <= X， Y <= 100000
> 
> 对于100%的数据, -1000000000 <= X, Y <= 1000000000

## 输出格式 ##

> 输出dis(X, Y)

## 样例输入 ##

0 1

## 样例输出 ##

## 资源约定： ##

峰值内存消耗（含虚拟机） < 256M

CPU消耗 < 1000ms

# 解题思路 #

我们可以将螺旋折线看成大正方形内有小的正方形。

我们认为`(0,0)`为第一个正方形的起点，将起点开始的第一个方格线向下翻折即可得到正方形

![正方形][05XI61.png]

> 由图可以知道第一个正方形结束的终点为`(-1,-1)`
> 
> 这时我们可以得到第t圈的正方形的终点为`(-t,-t)`
> 
> 那么第t个正方形本身的长度就为`8 * t`

那么我们考虑正方形的四个边长所构成的函数

分别为：`x = -t`，`x = t`，`y = -t`，`y = t`

![正方形][05X5lR.png]

这样就一目了然了

> 圈数 `t = max(abs(x), abs(y))`
> 
> 1、当`(x,y)`在`(-t,-t)`处时，即为第 t 个正方形的起点，第 t - 1 个正方形的终点，那么长度就为`ans = (8 + 8 * t) * t / 2`
> 
> 2、当不在`(-t,-t)`时，前 t - 1个正方形的长度为`dis = (8 + 8 * (t - 1)) * (t - 1) / 2`
> 
> 当`x = -t`时，`ans = dis + y + t`
> 
> 当`y = t`时，`ans = dis + 2 * t + x + t`
> 
> 当`x = t`时，`ans = dis + 4 * t + t - y`
> 
> 当`y = -t`时，`ans = dis + 6 * t + t - x`

# 解题代码 #

//
    //  main.cpp
    //  2018lanqiao-g
    //
    //  Created by 陈洋 on 2020/10/12.
    //  Copyright © 2020 陈洋. All rights reserved.
    //
    
    #include <iostream>
    #include <cmath>
    using namespace std;
    
    int main(int argc, const char * argv[]) {
        
        long long x,y;
        
        long long t,dis;
        long long ans = 0;
        
    //    while(1){
        
            cin >> x >> y;
            
            t = max(abs(x), abs(y));
            
            if(x == -t && y == -t){
        
                ans = (8 + 8 * t) * t / 2;
            }
            else{
        
                dis = (8 + 8 * (t - 1)) * (t - 1) / 2;
                if(x == -t){
        
                    ans = dis + y + t;
                }
                
                if(y == t){
        
                    ans = dis + 2 * t + x + t;
                }
                
                if(x == t){
        
                    ans = dis + 4 * t + t - y;
                }
                
                if(y == -t && x != -(t + 1)){
        
                    ans = dis + 6 * t + t - x;
                }
            }
            
            
            
            cout << ans << endl;
    //    }
    
    }

[05X4p9.png]: /images/20221120/db9277a0bbe74997ae5ac5cf63f949fb.png
[05XI61.png]: https://s1.ax1x.com/2020/10/14/05XI61.png
[05X5lR.png]: https://s1.ax1x.com/2020/10/14/05X5lR.png