分形之城

发表于 | 分类于 |

问题

城市的规划在城市建设中是个大问题。不幸的是，很多城市在开始建设的时候并没有很好的规划，城市规模扩大之后规划不合理的问题就开始显现。而这座名为Fractal的城市设想了这样的一个规划方案，如下图所示
ch1

当城区规模扩大之后，Fractal的解决方案是把和原来城区结构一样的区域按照图中的方式建设在城市周围，提升城市的等级。对于任意等级的城市，我们把正方形街区从左上角开始按照道路标号。

虽然这个方案很烂，Fractal 规划部门的人员还是想知道，如果城市发展到了等级 N，编号为 A 和 B 的两个街区的直线距离是多少。街区的距离指的是街区的中心点之间的距离，每个街区都是边长为 10 米的正方形。

输入格式

第一行输入正整数n，表示测试数据的数目。
以下n行，输入n组测试数据，每组一行。
每组数据包括三个整数 N,A,B, 表示城市等级以及两个街区的编号，整数之间用空格隔开。

输出格式

一共输出n行数据，每行对应一组测试数据的输出结果，结果四舍五入到整数。

数据范围

1≤N≤31,
1≤A,B≤22N,
1≤n≤1000

输入样例

3 
1 1 2 
2 16 1 
3 4 33

输出样例

10 
30 
50

思路

递归
关于递归

ch1
按照各个城区中心为坐标原点，于是每一个城市等级，它的中心都会发生变化。上图等级2的10号城区的坐标为(3, -3)。

按城区1的中心为原点，旋转平移后的坐标如下：

左上角：（x，y）关于原点顺时针90度旋转得到（y，-x）再关于y轴轴对称变换得到（-y，-x）；
右上角：（x，y）向右平移2len个单位得到（x+2len，y），len为两区域之间的长度；
右下角：（x，y）向右平移2len个单位得到（x+2len，y）再向下平移2len个单位得到（x+2len，y-2len）；
左下角：（x，y）逆时针旋转90度得到（-y，x），再关于y轴轴对称变换得到（y，x），最后再向下平移2len得到（y，x-2len）；

调整坐标原点，向右下角移动，具体操作为调整原来的坐标，横坐标减小len，纵坐标增加len。调整坐标原点后的坐标如下：

左上角：（-y，-x）改变坐标得到（-y-len，-x+len）；
右上角：（x+2len，y）变成（x+len，y+len）；
右下角：（x+2len，y-2len）变成 （x+len，y-len）；
左下角：（y，x-2len）变成（y-len，x-len）

旋转矩阵
递推型

  1. 前后关系：cal(n)与cal(n-1)
  2. 子问题状态：城市的级别n和城市的编号m
  3. 递归结果：有返回值pll，局部变量
  4. 递归出口：n == 0

代码

使用long long的数据范围
需要分块求其对应的位置，城市应该从0开始

调试过程

两次调用递归函数，导致TLE
pll pos = cal(n-1, m%cnt);
ll x = pos.first, y = pos.second;
//ll x = cal(n-1, m%cnt).first;
//ll y = cal(n-1, m%cnt).second;

#include <iostream>
#include <cmath>
using namespace std;
typedef long long ll; //数据范围较大,使用ll
typedef pair<ll, ll> pll;

//旋转时，各位置均看作原点
pll cal(ll n, ll m) //n级城市,第m+1个房子
{
    if (n == 0) return {0, 0};//递归出口n为0
    ll len = 1ll << (n - 1); //n级城市的两区域的相距长度，n为1时，len等于1
    ll cnt = 1ll << (2*n - 2) ; //n-1级城市,房子的总数
    pll pos = cal(n-1, m%cnt);  //m%cnt即该房子在n-1级城市的编号
    ll x = pos.first, y = pos.second;
    int z = m / cnt; //由z可得该房子位于哪个区域
    if (z == 0) return {y, x};
    else if (z == 1) return {x, y + len};
    else if (z == 2) return {x + len, y + len};
    return {2 * len - 1 - y, len - 1 - x};
}

int main()
{
    ll n, N, A, B;
    cin >> n;
    while(n--)
    {
        cin >> N >> A >> B;
        ll x1 = cal(N, A-1).first;  ll x2 = cal(N, B-1).first;
        ll y1 = cal(N, A-1).second; ll y2 = cal(N, B-1).second;
        ll dx = x1 - x2, dy = y1 - y2; //定义中间变量，缩短代码长度
        double ans = sqrt((dx * dx + dy * dy)) * 10; //最后乘10即可
        printf("%0.lf\n",ans);
    }
}