分形之城

膜拜大佬的题解：https://www.acwing.com/solution/content/16524/

递归+分治的思路好理解，因为这个题目中最显著的特点就是，不断地重复旋转复制，也就是N级城市，可以由4个N−1级城市构造，因此我们每次可以不断地分形N−1级，将问题范围不断地缩小

注意坐标是按照数组下标的方式来定的

 1 #include <bits/stdc++.h>
 2 using namespace std;
 3 typedef long long ll;
 4 typedef pair<ll, ll> PLL;
 5 PLL calc(ll n, ll m) {
 6     if (n == 0) {
 7         return make_pair(0, 0);
 8     }
 9     ll len = 1LL << (n - 1), cnt = 1LL << (2 * n - 2);
10     //cnt是子问题中的点的数量
11     //len是每个小单元的边长
12     PLL pos = calc(n - 1, m % cnt); //pos表示子问题的结果
13     ll x = pos.first, y = pos.second;
14     ll z = m / cnt; //z表示处理哪一部分
15     if (z == 0) { //处理左上角
16         return make_pair(y, x);
17     }
18     if (z == 1) { //处理右上角
19         return make_pair(x, y + len);
20     }
21     if (z == 2) { //处理右下角
22         return make_pair(x + len, y + len);
23     }
24     return make_pair(2 * len - 1 - y, len - 1 - x); //处理左下角
25 }
26 int main() {
27     int t;
28     cin >> t;
29     while (t--) {
30         ll n, a, b;
31         cin >> n >> a >> b;
32         PLL x = calc(n, a - 1);
33         PLL y = calc(n, b - 1); //都把下标变换成从0到n - 1
34         ll dx = x.first - y.first, dy = x.second - y.second;
35         double ans = (sqrt(dx * dx + dy * dy) * 10);
36         cout << fixed << setprecision(0) << ans << endl;
37     }
38     return 0;
39 }