Fracal Streets

eye

N - 1级图中每个点的坐标，能拓展到N级图 图1为1级图各编号对应的坐标： 图2为2级图各编号对那个的图标 做三件事情就能够完成坐标转换 ①确定2级图中的编号是指的2级图中的第几个1级图：用2级图 编号除以4（2^2(N-1)）能够确定编号 ②确定这个点位于一级图中的那个点:用2级图编号模4（2^2(N - 1)） ③讲当前点的x,y坐标拓展到全图的坐标，拓展规则下面会讲，此时需要知道，我知道了N -1级图的点的坐标，那我就能知道N级的图的点的坐标

边界条件&坐标转换规则

注意：从1级图开始拓展的时候我们是从左上方开始拓展的，我们会向右边向下边还有右下方进行拓展 所以一个很显然的拓展规则是如果对于右下方，我们直接（x + len,y + len）即可，右边直接是（x,y + len）即可（len = 2 ^ (N - 1)，比如求2级图直接加2即可） 转换规则我们是从中间状态得到的，然后我们可以验证边界条件是否也遵循这个规则，但是这里由于像更加直观，我们先来看边界的时候的转换情况： 假设0级图算出来的是（x,y）,1级图1号点是（x,y）,二号点 是（x,y + 1）,三号点是（x + 1,y + 1），四号点是（x + 1,y）;看起来很顺畅，真的规则是如此吗 考虑2级图和1级图： 不过前提是：我们是从左上方开始的递归 黑体字内容我也没理解，这里确实有点抽象 1.若处于左上的N-1级城市中，则需要把(x,y)所在的N-1级城市顺时针旋转90度，坐标变为(y,2N-1-x-1)，再水平翻转，坐标最终变为(y,x)。这就是该房屋在N 级城市中的位置。 2.若处于右上的N-1级城市中，则该房屋在N级城市中的位置应为(x,y+2N-1)。 3.若处于右下的N-1级城市中，则该房屋在N级城市中的位置应为(x十2N-1,y+2N-1). 4.若处于左下的N-1级城市中，则需要把(x,y)所在的N-1级城市逆时针旋转90度再水平翻转，坐标变为(2N-1-y-1,2N-1-x-1)。在N级城市中的位置还要把行号再加2N-1，最终得到(2N-y-1,2N-1-x-1)。

1级图和0级图的变换是否遵循规

#include <iostream>
#include <cmath>
#define x first
#define y second
using namespace std;
typedef long long LL;
typedef pair<LL, LL> PLL;

PLL calc(LL n, LL m) {
    if(n == 0) return {0, 0};
    LL len = 1ll << (n - 1); // n - 1级图构成n级图平移时的单位长度
    LL cnt = 1ll << (n - 1) * 2; // n - 1级图中所含的元素个数
    LL cnk = m / cnt; // 在n级图中，编号为m的元素所属块的编号
    LL idx = m % cnt; // 在n级图中，编号为m的元素在所属块中的编号
    PLL pos = calc(n - 1, idx); // 在n级图中，编号为m的元素在所属块中的坐标
    LL x = pos.x, y = pos.y;
    // 根据n级图中某个块的编号和这个块中某个元素的坐标，确定n - 1级图的坐标变换
    // 注意：离散坐标系跟实数坐标系有些许差别，不考虑这些差别
    // 结果必然是抓耳挠腮。hh
    if(cnk == 0) return {y, x}; // 没有平移，虽是旋转，坐标关系容易确定
    if(cnk == 1) return {x, y + len}; // 单纯平移
    if(cnk == 2) return {x + len, y + len}; // 单纯平移
    if(cnk == 3) return {len * 2 - y - 1, len - x - 1}; // 旋转又平移
}
int main() {
    int times;
    cin >> times;
    while(times--) {
        LL n, a, b;
        cin >> n >> a >> b;
        PLL pa = calc(n, a - 1);
        PLL pb = calc(n, b - 1);
        double x = pa.x - pb.x, y = pa.y - pb.y;
        printf("%.0lf\n", sqrt(x * x + y * y) * 10);
      
    }
    return 0;
}