分形之城

AcWing-98-分形之城

分析

见《进阶指南》第18页。

实现

#include <iostream>
#include <cmath>
using namespace std;

typedef long long LL;
typedef pair<LL, LL> PLL;

double dis (const PLL& a, const PLL& b) {
    double dx = a.first - b.first, dy = a.second - b.second;
    return sqrt(dx * dx + dy * dy);
}
PLL solve (LL n, LL m) { // 由编号求坐标
    if (n == 0) return { 0, 0 }; // 问题边界，等级为 0 的城市只有一间房屋
    LL length = 1LL << (n - 1); // 子城市的边长
    LL total = 1LL << (2 * (n - 1)); // 子城市的房屋数
    auto pos = solve(n - 1, m % total);
    LL x = pos.first, y = pos.second;
    LL z = m / total; // 房屋 m 在原城市中的区域编号（0、1、2、3）
    if (z == 0)
        return { y, x };
    else if (z == 1)
        return { x, y + length };
    else if (z == 2)
        return { x + length, y + length };
    else // z == 3
        return { -y + 2 * length - 1, -x + length - 1 };
}

int main () {
    int T;
    cin >> T;
    while (T --) {
        LL n, a, b;
        cin >> n >> a >> b;
        printf("%.0f\n", dis(solve(n, a - 1), solve(n, b - 1)) * 10);
    }
    return 0;
}