Fractal Streets

1.Fractal Streets

​​https://ac.nowcoder.com/acm/contest/998/G​​

题目大意：

思路：找规律。矩阵的四个象限对应的坐标转换不同。

#include <bits/stdc++.h>
#define endl '\n'
using namespace std;
struct point{
  long long x, y;
};

point get(long long n, long long a){
  if(n == 0) return {0, 0};
  long long block = 1ll << (n*2 - 2), len = 1ll << (n-1);
  auto p = get(n - 1, a % block);
  long long x = p.x, y = p.y;
  int z = a / block;
  
  if(z == 0) return {y, x};
  else if(z == 1) return {x, y + len};
  else if(z == 2) return {x + len, y + len};
  return {len * 2 - 1 - y, len - 1 - x};
}

int main(){
  cin.tie(0);cout.tie(0);
  
  int t;
  cin >> t;
  while(t--){
    long long n, a, b;
    cin >> n >> a >> b;
    auto pa = get(n, a - 1);
    auto pb = get(n, b - 1);
    double dx = pa.x - pb.x, dy = pa.y - pb.y;
      printf("%.0lf\n", sqrt(dx*dx + dy*dy) * 10);
        //这里四舍五入，必须用printf的%.0lf才对。直接cout不对，直接(long long)强转也不对
    
  }
  
  return 0;
}