Problem H
Fractal Area
The $1^{\mathrm{st}}$ iteration in the construction of the CS Fractal consists of a single circle of radius $r > 0$. In the $2^{\mathrm{nd}}$ iteration, this “parent” circle spawns four “child” circles of radius $r/2$ that are tangent to the parent circle in each of the north, south, east, and west directions. Now let $n \geq 3$. In the $n^{\mathrm{th}}$ iteration, each circle $C$ added in the $(n-1)^{\mathrm{st}}$ iteration spawns three child circles whose radii are exactly half of $C$’s radius, and that are tangent to $C$ in each of the three compass directions other than the direction in which $C$ touches its parent circle (here the compass directions are relatively to $C$). For example, in the $3^{\mathrm{rd}}$ iteration, the circle $C$ of radius $r/2$ that is north of the $1^\mathrm {st}$-generation circle spawns three circles of radius $r/4$ that touch $C$ in its west, north, and east directions. The illustration accompanying this problem depicts the CS Fractal after $6$ iterations. (Technically, the fractal is the shape generated after infinitely many iterations, but we informally use “fractal” to refer to the partially constructed shape after a finite number of iterations.)
Given the radius of the starting ($1^{\mathrm{st}}$-iteration) circle and the number of iterations, determine the area of the partially constructed fractal.
Note: Other than the single-point intersection between any child circle and its parent, no two circles in the fractal intersect.
Input
The first line of input contains an integer $T$, the number of test cases ($1 \leq T \leq 50$). This is followed by $T$ lines, one per test case, each of which contains two space-separated integers, $r$ and $n$ ($1 \leq r \leq 200$, $1 \leq n \leq 50$), where $r$ is the radius of the starting ($1^{\mathrm{st}}$-iteration) circle and $n$ is the number of iterations.
Output
For each test case, output the area of the partially constructed fractal with starting radius $r$ after $n$ iterations. Each computed area will be considered correct if it is within $10^{-6}$ of the official answer.
| Sample Input 1 | Sample Output 1 |
|---|---|
2 1 1 8 3 |
3.141592653589793 552.9203070318035 |
