Quote from Acwing, original link:

• 98. Fractal City

Directory:

• The title
• Answer key
• code

The title

Urban planning is a big problem in urban construction.

Unfortunately, many cities were not well planned at the beginning of construction, and the problem of unreasonable planning began to emerge as the city scale increased.

The Fractal city envisions just such a plan, as you can see below:

When urban areas expand, the Fractal solution is to build areas with the same structure as the original urban area around the city in the way shown in the picture, so as to upgrade the level of the city.

For any rank of city, we numbered the square blocks by road starting at the top left corner.

As bad as it is, the Fractal planning department wants to know what the straight-line distance between the two blocks, numbered AAA and BBB, will be if the city grows to scale NNN.

The distance of a block refers to the distance between the center points of a block. Each block is a square with sides of 101,010 meters.

Input format

In the following NNN lines, enter the NNN group of test data, one row for each group.

Each set of data contains three integers N,A,BN, A,BN, A,B, indicating the city level and the number of the two blocks, separated by Spaces.

The output format

A total of NNN lines of data are output, and each line corresponds to the output results of a set of test data, which are rounded to an integer.

Data range

• 
  $1 \le N \le 31$
• 
  $1 \le A,B \le 2^{2N}$
• 
  $1 \le n \le 1000$

Example Input:

3 
1 1 2 
2 16 1 
3 4 33 
Copy the code

Example output:

10 to 30 50Copy the code

Answer key

What’s wrong with that? Draw it hand by hand!

First, to clarify why recursion is used:

• We want to calculatenThe coordinates of the hierarchy, yesn-1The coordinates of the levels will do

And then think, how do I recurse?

Let us first stipulate that the origin of each coordinate system is unique, as shown below.

Then we generalize from the special to the general:

• The level 1 block, if you put it in level 2, there are four cases to talk about
• Level 1 in the upper left quadrant of Level 2 is rotated 90 degrees clockwise and flipped along the Y-axis (why flip along the Y-axis? Because you pay attention to the position of each number, do not flip, although the shapes are correct, but the numbering order is not correct.)
• If level 1 is placed in the upper right quadrant of Level 2, no rotation is required
• If level 1 is placed in the lower right quadrant of Level 2, no rotation is required
• Level 1 in the lower left quadrant of Level 2 is rotated 90 degrees counterclockwise and flipped along the Y-axis

That’s it, because now we’re going from level 1 to level 2, so the origin of the frame has moved, so we’re going to shift it from the original coordinates of level 1.

All right, let me draw you a picture so you get the idea.

And then you look at the code.

Here’s a bit of math:

• For the point(x, y), rotated 90° clockwise along the origin, will become(y, -x)
• For the point(x, y), rotated 90° counterclockwise along the origin, will become(-y, x)
• For the point(x, y), the Y-axis is the axis of symmetry and the flip will become(-x, y)

code

#include <iostream>
#include <cstring>
#include <cmath>  // sqrt
#include <algorithm>

using namespace std;

typedef long long LL;
typedef pair<LL, LL> PLL;

PLL calc(LL n, LL m)
{
    /* * n: level * m: coordinates, counting from 0 */
    if (n == 0) return {0.0};
    LL len = 1ll << (n - 1);  // 2^{n-1} The length of the inner quadrant of this level /2
    LL cnt = 1ll< < (2 * n - 2);  // 4^{n-1} Specifies the inner quadrant capacity of the level
    PLL pos = calc(n - 1, m % cnt);  // The coordinate information of the previous level
    LL x = pos.first, y = pos.second;
    int z = m / cnt;  // Which quadrant is in
    // Change the origin (-y-len,-x+len) along the y-symmetry (-y,-x)
    if (z == 0)
        return { - y - len, - x + len };
    // Change the origin of the upper right quadrant (x+len,y+len)
    else if (z == 1)
        return { x + len, y + len };
    // Change the origin of the lower right quadrant (x+len,y-len)
    else if (z == 2)
        return { x + len, y - len };
    // Change the origin (y-len,x-len) along the y-symmetry (y,x)
    return { y - len, x - len };
}

int main(a)
{
    int N;
    cin >> N;
    while (N --)
    {
        LL n, m1, m2;
        cin >> n >> m1 >> m2;
        PLL pos1 = calc(n, m1 - 1);
        PLL pos2 = calc(n, m2 - 1);

        double delta_x = (double) (pos1.first - pos2.first);
        double delta_y = (double) (pos1.second - pos2.second);
        // Level 1 len is the unit length and indicates that half the length of the quadrant is 10/2 = 5
        printf("%.0lf\n".sqrt(delta_x * delta_x + delta_y * delta_y) * 5); }}Copy the code