E: Fractal Area

https://open.kattis.com/problems/fractalarea

First, the area is $\pi r^2$ after the first iteration.

The second iteration starts with 4 circles of radius $r/2$. Each following iteration triples the number of circles and halves the radius. So, the area $S$ from the 2nd to nth iterations is computed by:

$S = 4 \pi (r/2)^2 + 12 \pi (r/4)^2 + ... + 4(3^{n-2})\pi(r/2^{n-1}) ^2$

Expanding gives:

$S = \pi r^2 + \frac{3}{4} \pi r^2 + \frac{9}{16} \pi r^2 + ... + \left( \frac{3}{4} \right)^{n-2} \pi r^2$

This is a geometric series, so we can get a closed form:

$S = 4 \pi r ^2 (1 - \left(\frac{3}{4}\right)^{n-1} )$

Therefore, the total area is

$A = \pi r^2 + 4 \pi r ^2 (1 - \left(\frac{3}{4}\right)^{n-1} )$

This can be computed as follows:

// compute area using the formula
double area = (pi * r * r) + 4 * pi * r * r * (1 - pow(0.75,n-1));

Note: computing (3/4)^(n-1) works well because doubles have good precision close to 0. Computing 3^(n-1) and 4^(n-1) individually then taking their quotient will lead to arithmetic overflow.