Quoted from Acwing, original title link:

  • The Fractal City


  • The title
  • Answer key
  • code

The title

The planning of cities is a big problem in urban construction. < / p > < p > unfortunately, when many cities at the start of construction, there is no good planning, city expansion planning after the unreasonable problems began to appear.

The Fractal city has developed a planning scheme that can be seen in the following image:

< P > As urban areas have grown in size, the Fractal solution has been to build similar areas around cities in the same way as the original urban structure in the image, raising the level of cities. < / p > < p > for any level of cities, we put a square blocks according to the road label from the top left corner.

Although the scheme is A poor one, the Fractal planning department has wondered what the distance between $A$and $B$blocks would be as the crow flies if the city grew to $N$.

The distance of a block is the distance between the center points of a block, and each block is a square with a side length of $10$meters.

input format

Input the first line of the positive integer $n$, representing the number of test data.

The following $n$line, enter $n$group test data, one row per group.

Each set of data consists of three integers, $N, A, and B$, representing the city level and the number of two blocks, separated by A space.

<h4> output format </h4>

A total of $n$rows of data are printed, each row corresponds to the output of a set of test data, and the results are rounded to an integer.

<h4> Data range </h4>

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

<h4> input sample: </h4>

3, 1, 1, 2, 2, 16, 1, 3, 4, 33

<h4> output sample: </h4>

10 to 30 50

Answer key

This has what do not understand, hand by hand to draw!

First, it’s clear why we use recursion:

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

And then think about how do we recurse?

Let us first specify that the origin of the coordinate system for each level is unique, as shown in the figure below.

Then we generalize the rule from the special to the general:

  • The level 1 block, if you put it in level 2, there are four situations that you want to talk about
  • If level 1 is placed in the upper left quadrant of level 2, it is rotated 90 degrees clockwise and also flipped along the Y-axis (why would it be flipped along the Y-axis? Because you pay attention to the position of each number, do not flip, although the shape is 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
  • When level 1 is placed in the lower left quadrant of level 2, it is rotated counterclockwise by 90 degrees and is also rotated along the Y-axis

We’re done, because now we’re going from level one to level two, so the origin of the frame has been moved, so we’re going to shift it based on the original coordinates of level one.

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

Then you can look at the code.

Here’s a little math:

  • For the point(x, y), rotated 90° clockwise about the origin, will become(y, -x)
  • For the point(x, y), rotation 90° counterclockwise about the origin, will be(-y, x)
  • For the point(x, y), the Y-axis is taken as the axis of symmetry(-x, y)


#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: count from 0 */ if (n == 0) return {0, 0}; LL len = 1ll << (n - 1); // 2^{n-1} /2 LL CNT = 1ll << (2 * n-2); // 4^{n-1} PLL pos = calc(n-1, m % CNT); }}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}} int z = m / cnt; If (z == 0) return {-y-len,-x+len}; if (z == 0) return {-y-len,-x+len}; (x+len,y+len) else if (z == 1) return {x+len,y+len}; (x+len,y-len) else if (z == 2) return {x+len,y-len}; Return {y-len,x-len}; return {y-len,x-len}; return {y-len,x-len}; } int main() { 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); Printf ("%.0lf\n", SQRT (delta_x * delta_x + delta_y * delta_y) * 5); printf("%.0lf\n"); }}