Divide and conquer on four quadrants

September 20, 2026 · algorithms

Split level N into four quadrants. Each one is the previous city after a map. The turns are the usual rotation matrix at ±π/2.

AcWing 98, Fractal City. A city of level $N$ . Blocks numbered along a road. I want the straight-line distance between the centers of blocks $A$ and $B$ . Each cell is a $10\,\mathrm{m}$ block; the numbers are the ids along the road.

N = 1:

  1 ---- 2
         |
  4 ---- 3

N = 2 (four N=1 copies planted around, the road joining them end to end):

   1     4 --  5 --  6
   |     |           |
   2 --  3     8 --  7
               |
  15 -- 14     9 -- 10
   |     |           |
  16    13 -- 12 -- 11

Same picture as a grid of ids:

    1   4   5   6
    2   3   8   7
   15  14   9  10
   16  13  12  11

N = 3 (four N=2 copies, same planting):

   1 --  2    15 -- 16 -- 17    20 -- 21 -- 22
         |     |           |     |           |
   4 --  3    14 -- 13    18 -- 19    24 -- 23
   |                 |                 |
   5     8 --  9    12    31 -- 30    25 -- 26
   |     |     |     |     |     |           |
   6 --  7    10 -- 11    32    29 -- 28 -- 27
                           |
  59 -- 58    55 -- 54    33    36 -- 37 -- 38
   |     |     |     |     |     |           |
  60    57 -- 56    53    34 -- 35    40 -- 39
   |                 |                 |
  61 -- 62    51 -- 52    47 -- 46    41 -- 42
         |     |           |     |           |
  64 -- 63    50 -- 49 -- 48    45 -- 44 -- 43

Same picture as a grid of ids:

    1   2  15  16  17  20  21  22
    4   3  14  13  18  19  24  23
    5   8   9  12  31  30  25  26
    6   7  10  11  32  29  28  27
   59  58  55  54  33  36  37  38
   60  57  56  53  34  35  40  39
   61  62  51  52  47  46  41  42
   64  63  50  49  48  45  44  43

$N$ goes up to $31$ . There are $4^{N}$ blocks. I am not drawing that.

Two points

The distance is Euclidean, then rounded to an integer. If I have the two centers, I am done. The whole job is: given a level and a block id, find the center. Origin at the city center, $x$ right, $y$ up.

Level $1$ I can write down:

\begin{aligned} 1 &\mapsto (-5, 5), \\ 2 &\mapsto (5, 5), \\ 3 &\mapsto (5, -5), \\ 4 &\mapsto (-5, -5). \end{aligned}

Split, then ask what changed

There is a divide-and-conquer move here. Cut the level- $N$ city into four quadrants. Each quadrant has

q = 4^{N-1}

blocks — a whole city of level $N-1$ . The first $q$ ids live northwest, the next $q$ northeast, then southeast, then southwest, the same order the road already used at level $1$ .

So I recurse: which quadrant, then a smaller city. The remaining job is to look at that copy against the previous city and write down the map that was applied — numbering, rotation, shift.

A copy of level $N-1$ has side $2^{N-1}$ blocks. Its own center sits halfway from the parent center to the parent corner, so the shift is

d = 2^{N-2} \cdot 10.

The rotation matrix

A rotation of the plane by $\theta$ (counterclockwise positive) is

R(\theta) = \begin{pmatrix} \cos\theta & -\sin\theta \\ \sin\theta & \cos\theta \end{pmatrix}, \qquad R(\theta) \begin{pmatrix} x \\ y \end{pmatrix} = \begin{pmatrix} x\cos\theta - y\sin\theta \\ x\sin\theta + y\cos\theta \end{pmatrix}.

Plug in $\theta = -\pi/2$ : $\cos(-\pi/2) = 0$ , $\sin(-\pi/2) = -1$ , and

(x,y) \mapsto (y,\ -x).

That is $90^\circ$ clockwise.

Plug in $\theta = \pi/2$ : $\cos(\pi/2) = 0$ , $\sin(\pi/2) = 1$ , and

(x,y) \mapsto (-y,\ x).

That is $90^\circ$ counterclockwise.

The east copies keep the previous city as it was: only a shift. The west copies turn.

Four maps

Look at the northwest of $N=2$ in the picture: $1$ down to $2$ across to $3$ up to $4$ . The road walks this copy backwards versus level $1$ , and the square has been turned clockwise. Same reverse numbering in the southwest, turned the other way.

Northwest, $1 \le a \le q$ . Local id $a$ maps to $q+1-a$ . Rotate by $-\pi/2$ , shift by $(-d,d)$ :

a' = q + 1 - a, \qquad (x,y) \mapsto (y - d,\ -x + d).

Northeast, $q < a \le 2q$ . Same orientation, shift by $(d,d)$ :

a' = a - q, \qquad (x,y) \mapsto (x + d,\ y + d).

Southeast, $2q < a \le 3q$ . Same orientation, shift by $(d,-d)$ :

a' = a - 2q, \qquad (x,y) \mapsto (x + d,\ y - d).

Southwest, $3q < a \le 4q$ . Local id $i = a - 3q$ , then the same reverse $a' = q+1-i$ . Rotate by $\pi/2$ , shift by $(-d,-d)$ :

a' = q + 1 - (a - 3q), \qquad (x,y) \mapsto (-y - d,\ x - d).

Check block $1$ at level $2$ . Then $q = 4$ , $d = 10$ , northwest, $a' = 4$ . Level $1$ block $4$ is $(-5,-5)$ , and

(-5 - 10,\ -(-5) + 10) = (-15, 15).

Block $16$ : southwest, $i = 4$ , $a' = 1$ . Level $1$ block $1$ is $(-5,5)$ , and

(-5 - 10,\ -5 - 10) = (-15, -15).

Distance $30$ . That is the sample.

I only ever recurse on the level, so one query is $O(N)$ .

const int kBlockSideMeters = 10;

struct BlockCenter {
  long long x;
  long long y;
};

[[nodiscard]] BlockCenter find_block_center(int city_level,
                                            long long block_id) {
  if (city_level == 1) {
    if (block_id == 1) {
      return BlockCenter{.x = -kBlockSideMeters / 2, .y = kBlockSideMeters / 2};
    }

    if (block_id == 2) {
      return BlockCenter{.x = kBlockSideMeters / 2, .y = kBlockSideMeters / 2};
    }

    if (block_id == 3) {
      return BlockCenter{.x = kBlockSideMeters / 2, .y = -kBlockSideMeters / 2};
    }

    return BlockCenter{.x = -kBlockSideMeters / 2, .y = -kBlockSideMeters / 2};
  }

  // 4^(city_level - 1) = 2^(2*(city_level-1))
  long long blocks_per_quadrant = 1LL << (2 * (city_level - 1));

  // Offset from city center to a quadrant center: 2^(city_level-2) blocks *
  // 10m.
  long long quadrant_offset = (1LL << (city_level - 2)) * kBlockSideMeters;

  if (block_id <= blocks_per_quadrant) {
    // First quadrant: the road walks this copy backwards vs. the previous
    // level (see the N=1 / N=2 diagram). Local id i maps to
    // blocks_per_quadrant + 1 - i.
    long long subcity_block_id = blocks_per_quadrant - block_id + 1;
    auto subcity_center = find_block_center(city_level - 1, subcity_block_id);

    return BlockCenter{.x = subcity_center.y - quadrant_offset,
                       .y = -subcity_center.x + quadrant_offset};
  }

  if (block_id <= 2 * blocks_per_quadrant) {
    long long subcity_block_id = block_id - blocks_per_quadrant;
    auto subcity_center = find_block_center(city_level - 1, subcity_block_id);

    return BlockCenter{.x = subcity_center.x + quadrant_offset,
                       .y = subcity_center.y + quadrant_offset};
  }

  if (block_id <= 3 * blocks_per_quadrant) {
    long long subcity_block_id = block_id - (2 * blocks_per_quadrant);
    auto subcity_center = find_block_center(city_level - 1, subcity_block_id);

    return BlockCenter{.x = subcity_center.x + quadrant_offset,
                       .y = subcity_center.y - quadrant_offset};
  }

  // Fourth quadrant: same reverse numbering as the first quadrant.
  long long local_id = block_id - (3 * blocks_per_quadrant);
  long long subcity_block_id = blocks_per_quadrant + 1 - local_id;
  auto subcity_center = find_block_center(city_level - 1, subcity_block_id);

  return BlockCenter{.x = -subcity_center.y - quadrant_offset,
                     .y = subcity_center.x - quadrant_offset};
}

[[nodiscard]] int distance_between_blocks(int city_level, long long block_id_a,
                                          long long block_id_b) {
  auto center_a = find_block_center(city_level, block_id_a);
  auto center_b = find_block_center(city_level, block_id_b);
  double delta_x = static_cast<double>(center_a.x - center_b.x);
  double delta_y = static_cast<double>(center_a.y - center_b.y);
  return static_cast<int>(std::lround(std::hypot(delta_x, delta_y)));
}