This can be solved using **Green’s Theorem**, with a complexity of n^2log(n).

If you’re not familiar with the **Green’s Theorem** and want to know more, here is the video and notes from Khan Academy. But for the sake of our problem, I think my description will be enough.

The general equation of Green’s Theorem is

\Huge\mathbf{\oint_{C} (Ldx + Mdy) = \iint_{R}(\frac{\partial M}{\partial x} - \frac{\partial L}{\partial y})dxdy}

If I put *L* and *M* such that

\huge\mathbf{\frac{\partial M}{\partial x} - \frac{\partial L}{\partial y} = 1}

then the RHS is simply the area of the Region *R* and can be obtained by solving the closed integral or LHS and this is exactly what we’re going to do.

So Integrating along the path in the anticlockwise gives us the **Area** of the region and integrating along the clockwise gives us negative of the **Area**. So

**AreaOfUnion** = (Integration along red arcs in anticlockwise direction + Integration along blue arcs in clockwise direction)

But the cool trick is if for each circle if we integrate the arcs which are not inside any other circle we get our required area i.e. we get integration in an anticlockwise direction along all red arcs and integration along all blue arcs along the clockwise direction. **JOB DONE!!!**

Even the cases when a circle doesn’t intersect with any other is taken

care of.

Here is the GitHub link to my C++ Code