### jlcastrillon's blog

By jlcastrillon, 6 years ago, ,

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

•
• +24
•

 » 6 years ago, # |   +9 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, # |   +14 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, # ^ |   0 please describe any of them....
•  » » 6 years ago, # ^ |   +1 How do you do the "easy" part in less than O(N)? :)
 » 6 years ago, # |   0 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.
 » 7 months ago, # |   0 are there questions based on area similar to this on CodeForces?
•  » » 7 months ago, # ^ |   0 You can try this (not exactly same but similar): https://codeforces.com/contest/814/problem/D
 » 7 months ago, # | ← Rev. 2 →   +18 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.