8463:Stupid cat Doge ⑤

Stupid cat Doge ⑤"/>

8463:Stupid cat Doge ⑤

描述
动物园的规划和城市规划一样是个令人头疼的大问题。不幸的是，动物园规划师R.V.L.先生高估了小动物们的智商，他设计了一个极其复杂的动物园道路规划方案，如下图所示：

动物园按照下述方法进行扩建：当动物园规模扩大之后，R.V.L.先生设计的解决方案是把与原来动物园结构一样的区域复制或旋转90度之后按照图中的方式建设在原来的动物园周围（即将原来的动物园复制一遍放在原动物园上方，将顺时针旋转90度后的动物园放在原动物园的左上方，将逆时针旋转90度后的动物园放在原动物园的左方），再用道路将四部分的首尾连接起来，即可提升动物园的等级。

容易看出，等级提升后的动物园仍然是由一条道路连接，等级为N的动物园共能容纳2^2N只小动物，每只小动物将被分配到唯一的一间房屋。对于任意等级的动物园，我们从左上角开始沿着唯一的道路走，按照道路为房屋标号，就能够得到每间房屋的编号了。

说了这么多，智商余额不足的Stupid cat和Doge早已晕头转向。他们想知道，如果城市发展到了一定等级，他俩各自所处的房屋之间的直线距离是多少。房屋之间的距离是指两座房屋中心点之间的距离，你可以认为每间房屋都是边长为10米的正方形。

输入
输入包含多组测试数据，第一行有一个整数 T 表示测试数据的数目。
每组测试数据包含一行用空格隔开的三个整数 N, S, D，表示动物园等级，Stupid cat分配到的房屋编号和Doge分配到的房间编号。
输出
对于每组测试数据，在单独的一行内输出答案，四舍五入到整数。
样例输入
3
1 1 2
2 16 1
3 4 33
样例输出
10
30
50
提示
【数据范围】
N≤31，1≤S,D≤2^2N，1≤T≤10000.

解题

思路是把图不断分成4小块，然后看动物在哪个块上，然后根据每块图的逻辑计算出xy地址，然后两只动物的xy即可求出距离

分为两部分思考

• 图分块
  因为知道了等级，就能算出图的大小，把他分为4块，用动物的位置，即可求出动物在哪块，然后再在小块上细分
• 图位置的逻辑
  1234块，23是相同的，3是初始位置，
  将3沿左上至右下轴旋转即为1的位置，就是x和y交换
  将块的长度减去1的坐标即为第4块的坐标

参见

代码

#include <cmath>
#include <iostream>
using namespace std;
typedef long long ll;
int map[5][2] = {{0, 0}, {0, 0}, {0, 1}, {1, 1}, {1, 0}};
void find_how(ll i, ll n, ll &x, ll &y) {//找到如何来变换if (i == 1 || i == 4) {ll temp = x;x = y;y = temp;}if (i == 4) {ll temp = pow(2, n);x = temp - x - 1;y = temp - y - 1;}
}
void find_xy(ll n, ll animal, ll &x, ll &y) {//找到x和y的值if (n == 0)return;ll one_block = pow(2, 2 * (n - 1));//一块的大小ll i;for (i = 1; i <= 4; i++)if (one_block * i >= animal)break;find_xy(n - 1, animal - (i - 1) * one_block, x, y);find_how(i, n - 1, x, y);x += pow(2, n - 1) * map[i][0];y += pow(2, n - 1) * map[i][1];
}
int main() {int t;cin >> t;while (t--) {ll n, s, d;cin >> n >> s >> d;ll sx = 0, sy = 0, dx = 0, dy = 0;find_xy(n, s, sx, sy);find_xy(n, d, dx, dy);ll ans = round(sqrt(pow((sx - dx), 2) + pow((sy - dy), 2)) * 10);cout << ans << endl;}
}