原题题号：1697

• 题目描述

琦玉老师发现了一张藏宝图，
藏宝图是一张边长为n2个点，编号分别是n2。琦玉老师发现编号1，2，...，n2是从外层至中心按顺时针方向螺旋排列。琦玉老师开始去寻宝，他在编号为a的点出发，宝藏在编号为b的点，假设相邻的点对距离都是1，现在琦玉老师的问题是：从a点到b点的最短距离是多少？
如n = 3的时候，藏宝图各点位置如下：

此图中，编号2和编号5的最短距离就是sqrt（1＋4)= 2.236
如n = 5的时候，藏宝图个点位置如下：

如图中，编号5和 编号13的最短距离就是sqrt（16＋16）= 5.657

• 输入

先输入一个T（T≤1000），表示数据组数。
接下来T行，每行包括3个正整数n，a，b(1≤n≤4500，1≤a，b≤n2)。n表示藏宝图的边长，a表示琦玉老师所在的位置，b表示宝藏所在的位置。

• 输出

每组数据输出一行，包含一个浮点数，保留小数点后3位。（使用double类型）

• 样例输入

3
2 1 3
3 2 5
5 5 13

• 样例输出

1.414
2.236
5.657
此题一开始直接暴力模拟，结果超时，看来不能这么做，需要进行一些优化。
想到我们可以知道地图每一圈的长度，如果我们的起点或终点都不在此圈上，则直接进入下一圈，这样可以节省不少时间，尤其是地图比较大的时候。因为实际上每一圈都是从左上角开始的，因此发现需要的点在某个圈上的时候，只需要从这一圈的左上角开始走模拟即可，速度大大提升了。完整代码如下：

#include <iostream>
#include <cstdio>
#include <cmath>
typedef long long ll;
typedef long double ld;
using namespace std;
 
struct point
{
    int x, y;
    point() : x(0), y(0){};
    point(int arg1, int arg2) : x(arg1), y(arg2){};
    double dis(point &another)
        {return sqrt((this->x - another.x) * (this->x - another.x) + (this->y - another.y) * (this->y - another.y));}
};
 
void gogogo(int &num,int &square,int &a,char how)
{
    if(square<num)
        for (int i = 1; i < square;i++)
        {
            num--;
            if(how=='+')
                a++;
            else
                a--;
        }
    else
    {
        for (int i = 1; i < num;i++)
            if(how=='+')
                a++;
            else
                a--;
        num = 0;
    }     
}
 
void tofind(int num,int square,point &poi)
{
    while(num)
    {
        if((num-square*square+(square-2)*(square-2))>0&&square!=1)
        {
            num -= square * square - (square - 2) * (square - 2);
            poi.x++;
            poi.y++;
            square -= 2;
        }
        else
        {
            gogogo(num, square, poi.x, '+');
            gogogo(num, square, poi.y, '+');
            gogogo(num, square, poi.x, '-');
            gogogo(num, square, poi.y, '-');
        }
    }
}
 
int main()
{
    int t;
    cin >> t;
    while(t--)
    {
        int square, p1, p2;
        cin >> square >> p1 >> p2;
        point a, b;
        a.x = a.y = b.x = b.y = 1;
        tofind(p1, square, a);
        tofind(p2, square, b);
        printf("%.3f\n", a.dis(b));
    }
    //system("pause");
    return 0;
}

实际上，该解法仍能优化，可以看到tofind函数运行了两次，但实际上只需要运行一次，有时间我会再进行优化。

本文作者：TTQ
本文链接：https://blog.ponder.fun/archives/18.html
最后修改时间：2020-02-09 12:20:26
本站未注明转载的文章均为原创，并采用 CC BY-NC-SA 4.0 授权协议，转载请注明来源，谢谢！