P18 递归 找规律
- 左上角的图形相当于原图顺时针旋转90
- 左下角的图形相当于原图逆时针旋转90
计算坐标
旋转图形相当于旋转坐标轴
设当前点为(x, y)
1. 顺时针旋转90的坐标为(y, 2^(n-1) - x - 1)
2. 逆时针旋转90的坐标为(2^(n-1) - y - 1, x)
#include <bits/stdc++.h>
#define int long long
using namespace std;
pair<int, int> calc(int n, int m) {
if (n == 0) return {0, 0};
int len = 1LL << (n-1);
int cnt = 1LL << (2*n-2);
pair<int, int> pos = calc(n-1, m % cnt);
int z = m / cnt;
int x = pos.first; int y = pos.second;
if (z == 0) return {y, x};
if (z == 1) return {x, y+len};
if (z == 2) return {x+len, y+len};
if (z == 3) return {2*len-y-1, len-x-1};
}
signed main() {
int t;
cin >> t;
while (t--) {
int n;
cin >> n;
int a, b;
cin >> a >> b;
a--;
b--;
pair<int, int> posa = calc(n, a);
pair<int, int> posb = calc(n, b);
int x1 = posa.first, y1 = posa.second, x2 = posb.first, y2 = posb.second;
double ans = (1.0*sqrt((x1-x2)*(x1-x2) + (y1-y2)*(y1-y2)) * 10);
printf("%.0f\n", ans);
}
}