Thread: Over lapping circles

Originally Posted by C_ntua

Are you allowed to use common APIs or libraries? For example make a full screen program that draws the circles as red in white background, capture a screenshot (from code), save screenshot in a bitmap and count the red pixels and you are done.

Isn't it obvious that it's a contest? You are usually limited to standard input/output and pure single-threaded computations.

There are three approaches:
1. Analytical - requires advanced math.
2. Numerical - requires less math, but not as accurate.
3. Per pixel checking - simple to implement, but extremely inefficient. In this case it would require 100 * 1000 * 100 * 1000 bits (precision to 3 decimal places), which is over one GB of memory.

The approach 2 would since be preffered, through it requires basic knowledge of constructive solid geometry (limited to 2D in this case). All you need is to divide each circle into a sensible number of segments and implement sum operation. Having that, you need to compute the area of the constructed figures (note: there can be more than one). Both operations can be googled.