I have different circles with their x,y co-ordinates and radius.What is the algorithm that I can find the area covered by the circles. does this need integral calculus? the problem description is here..http://uva.onlinejudge.org/index.php...m&problem=3208 . Which branches of programming should I know to solve this problem. Does the basics like loop,array,vector,map etc will help? or I need to know more than this!
Last edited by Tamim Ad Dari; 05-01-2013 at 01:47 AM.
Circular segment - Wikipedia, the free encyclopedia
For two circles, construct a line (making a chord) between the two intersection points.
From that, you can work out two areas for the segment of each circle, and adding these two together is the area of the overlap.
The rest is just the area of two circles.
If you dance barefoot on the broken glass of undefined behaviour, you've got to expect the occasional cut.
If at first you don't succeed, try writing your phone number on the exam paper.
more than two? about 14-15?
It's called a for loop.Originally Posted by Tamim Ad Dari
If you dance barefoot on the broken glass of undefined behaviour, you've got to expect the occasional cut.
If at first you don't succeed, try writing your phone number on the exam paper.
The problem is not finding the area of two overlapping circles (which is a straight formula). The problem appears when you have two overlapping circles (A and B), and you want to add a third one (C). You cannot simply add the area:
C - overlap(C, A) - overlap(C, B)
because you have to take into account overlap(A, B).
Last edited by kmdv; 05-02-2013 at 02:20 PM.
I would work at it from reverse; figure out the total area that can be bombed.
Then keep track of the un-bombed area after each bomb.
No idea if it is easier or will work; but it seems like a way worth trying.
Tim S.
"...a computer is a stupid machine with the ability to do incredibly smart things, while computer programmers are smart people with the ability to do incredibly stupid things. They are,in short, a perfect match.." Bill Bryson
Owh.. I got that.. not an easy problem though...
Not only overlap(C,A) and (C,B) will do... You have to also calculate overlap(A,B,C)...
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.
nope... not allowed to do so..
Here is an article related to a closed form (i.e. a formula) for computing area of overlap of three overlapping circles. That publication dates from 2006, so I doubt you'll find a lot of information about formulae for four or more overlapping circles.
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.
Last edited by kmdv; 05-03-2013 at 07:53 AM.
