分形之城

思路：将一个大城区分成四个小城区，先计算出计算点在左上角小城区里的相对位置，再根据坐标变换得到正确位置

观察得到坐标变换规律：当城区规模扩大一级时，定义len为小城区的长度，则有

• 第一象限的点：{x, y} -> {y, x};
• 第二象限的点：{x, y} -> {x, y + len}
• 第三象限的点：{x, y} -> {x + len, y + len}
• 第四象限的点：{x, y} -> {len * 2 - 1 - x, len - 1 - y}

#include<bits/stdc++.h>
using namespace std;
#define int long long
typedef pair<int, int> PII;

PII cal(int n, int m){
    if(n == 0) return {0, 0};
    int len = 1ll << (n - 1);
    int num = 1ll << 2*(n - 1);
    PII pos = cal(n - 1, m % num);
    int x = pos.first, y = pos.second;
    int dim = m / num; // 位于哪一个象限
    if(dim == 0) return {y, x}; // 左上
    if(dim == 1) return {x, y + len}; // 右上
    if(dim == 2) return {x + len, y + len}; // 右下
    if(dim == 3) return {len * 2 - 1 - y, len - 1 - x}; // 左下
}

signed main(){
    ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    int T;
    cin >> T;
    while(T --){
        int n, A, B;
        cin >> n >> A >> B;
        PII pos1 = cal(n, A - 1);
        PII pos2 = cal(n, B - 1);
        double x = (pos1.first - pos2.first) * 10;
        double y = (pos1.second - pos2.second) * 10;
        cout << fixed << setprecision(0) << sqrt(x*x + y*y) << '\n';
    }
    return 0;
}