> For the complete documentation index, see [llms.txt](https://solutions.icpc.uclaacm.com/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://solutions.icpc.uclaacm.com/2021-tryout-solutions/tryout-2-solutions/e-fractal-area.md).

# 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:

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

{% hint style="info" %}
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.**
{% endhint %}