With a growing desire for modernization in our increasingly larger cities comes a need for new street designs. Chris is one of the unfortunate city planners responsible for these designs. Each year the demands keep increasing, and this year he has even been asked to design a completely new city. More work is not something Chris needs right now, since like any good bureaucrat, he is extremely lazy. Given that this is a character trait he has in common with most computer scientists it should come as no surprise that one of his closest friends, Paul, is in fact a computer scientist. And it was Paul who suggested the brilliant idea that has made Chris a hero among his peers: Fractal Streets! By using a Hilbert curve, he can easily fill in rectangular plots of arbitrary size with very little work.

A Hilbert curve of order 1 consists of one "cup". In a Hilbert curve of order 2 that cup is replaced by four smaller but identical cups and three connecting roads. In a Hilbert curve of order 3 those four cups are in turn replaced by four identical but still smaller cups and three connecting roads, etc. At each corner of a cup a driveway (with mailbox) is placed for a house, with a simple successive numbering. The house in the top left corner has number 1, and the distance between two adjacent houses is 10m. The situation is shown graphically in figure 2. As you can see the Fractal Streets concept successfully eliminates the need for boring street grids, while still requiring very little effort from our bureaucrats. As a token of their gratitude, several mayors have offered Chris a house in one of the many new neighborhoods built with his own new scheme. Chris would now like to know which of these offerings will get him a house closest to the local city planning office (of course each of these new neighborhoods has one). Luckily he will not have to actually drive along the street, because his new company "car" is one of those new flying cars. This high-tech vehicle allows him to travel in a straight line from his driveway to the driveway of his new office. Can you write a program to determine the distance he will have to fly for each offier (excluding the vertical distance at takeoff and landing)?

Input

On the first line of the input is a positive integer, the number of test cases. Then for each test case: A line containing a three positive integers, n < 32 and h, o < 231, specifying the order of the Hilbert curve, and the house numbers of the offered house and the local city planning office.

Output

For each test case: One line containing the distance Chris will have to fly to his work in meters, rounded to the nearest integer.

Input Example:

3
1 1 2
2 16 1
3 4 33

Output Example:

10
30
50

题目分析

首先为了方便取模运算, 我们将编号都减 1 ,即从0 开始编号。 仔细观察等级1和等级2。我们可以发现: 等级2的左上角的图像是通过顺时针旋转90度等级1的图像再左右翻转得到的。 等级2的右上角的图像是等级1的图像。 等级2的右下角的图像是等级1的图像。 等级2的左下角的图像是通过逆时针旋转90度等级1的图像再左右翻转得到的。

  • 对于点 (x, y) ,沿原点顺时针旋转 90° ,将变为 (y, -x)
  • 对于点 (x, y) ,沿原点逆时针旋转 90° ,将变为 (-y, x)
  • 对于点 (x, y) ,以 y 轴为对称轴翻转将变为 (-x, y)

我们假设对应在等级一的坐标为(x, y),那么对于升级后的图像的坐标(不考虑x, y 轴的偏移量): 等级2的左上角的图像所对应的坐标:(y, x) 等级2的右上角的图像所对应的坐标:(x, y) 等级2的右下角的图像所对应的坐标:(x, y) 等级2的左下角的图像所对应的坐标:(len - y - 1, len - x - 1) 我们再加上偏移量len(等级1的图像的边长),可以得到: 等级2的左上角的图像所对应的坐标:(y, x) 等级2的右上角的图像所对应的坐标:(x, y + len) 等级2的右下角的图像所对应的坐标:(x + len, y + len) 等级2的左下角的图像所对应的坐标:(len - y - 1 + len, len - x - 1)

观察完了等级1, 等级2, 我们再观察等级3。 会发现这是一个低等级到高等级递归的过程。 那么对于等级 N 的 第 idx 个点: 我们可以知道 等级 N - 1 一共有 cnt = (1 << (2 * level - 2)) 个点, 边长(偏移量)为 sqrt(cnt)。 对于这的点 idx ,我们可以知道它在 等级 N 的左上还是右上还是右下还是左下区域。(idx / cnt) 我们可以递归得到 等级 N - 1 时对于的点的坐标。(calc(level - 1, idx

那么我们可以根据它在 等级 N 的具体区域,进行适当的坐标钻换即可得到正确答案。

代码实现

#include <iostream>
#include <cmath>
#define x first
#define y second
using namespace std;
using LL = long long;
using PLL = pair <LL, LL>;

LL t, n, a, b;
PLL calc(int level, LL idx) {
    if(!level) return {0,0};
    LL len = 1ll << (level - 1), cnt = 1ll << (2 * level - 2);
    PLL pos = calc(level - 1, idx
    int z = idx / cnt;
    if(z == 0) return {pos.y, pos.x};
    if(z == 1) return {pos.x, pos.y + len};
    if(z == 2) return {pos.x + len, pos.y + len};
    return {len * 2 - pos.y - 1, len - pos.x - 1};
}
void solve() {
    cin >> n >> a >> b;
    PLL coordinateA = calc(n, a - 1);
    PLL coordinateB = calc(n, b - 1);
    double dx = coordinateA.x - coordinateB.x;
    double dy = coordinateA.y - coordinateB.y;
    printf("
}
int main () {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cin >> t;
    while(t--) solve();
    return 0;
}

0 条评论

发表回复

Avatar placeholder

您的电子邮箱地址不会被公开。 必填项已用*标注

友情链接:Ctips' blog, Colza’s blog

站点状态:Status