jlcastrillon's blog

By jlcastrillon, 6 years ago, In English,

Given n circles n <= 1000, how can I find the area of union of all this circles?

 
 
 
 
  • Vote: I like it  
  • +24
  • Vote: I do not like it  

»
6 years ago, # |
  Vote: I like it +9 Vote: I do not like it

I'm interested in that kind of problem too..! http://www.spoj.pl/problems/VCIRCLES/ is a small version but the big one is http://www.spoj.pl/problems/CIRU/

»
6 years ago, # |
  Vote: I like it +14 Vote: I do not like it

The main idea here is to make a vertical decomposition: draw a vertical line through every point of two circles' intersection and through two points with maximal and minimal x of every circle. Hence, you'll have O(N^2) vertical bands. In each band you have something like brackets (arcs) sequence so you can skip inner brackets. At last, you have some trapezoids with arc as side edges. Their area can be easily found in many ways.

»
6 years ago, # |
  Vote: I like it 0 Vote: I do not like it

There is a way, I think. But I never implemented it myself. You can try to build planar graph where vertices are points of circles intersections and edges are arcs. Then you can use standard algorithm for finding the area of faces of the planar graph. The only problem is how to sort edges, connected to one vertex. I am not sure about how do it correctly.

»
2 months ago, # |
  Vote: I like it 0 Vote: I do not like it

are there questions based on area similar to this on CodeForces?

»
2 months ago, # |
Rev. 2   Vote: I like it +18 Vote: I do not like it

This problem can be solved with Green’s Theorem : Find the arcs which lies in the border of the union of area (in n^2lgn time with sweep), and apply the formula directly.