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

# | User | Rating |
---|---|---|

1 | tourist | 3434 |

2 | Petr | 3353 |

3 | OO0OOO00O0OOO0O0…O | 3314 |

4 | fateice | 3306 |

5 | Um_nik | 3286 |

6 | Syloviaely | 3274 |

7 | dotorya | 3145 |

8 | LHiC | 3114 |

9 | Radewoosh | 3098 |

10 | mnbvmar | 3096 |

# | User | Contrib. |
---|---|---|

1 | tourist | 178 |

2 | rng_58 | 167 |

3 | Petr | 156 |

4 | csacademy | 155 |

5 | Swistakk | 150 |

6 | lewin | 149 |

7 | Um_nik | 141 |

7 | Errichto | 141 |

9 | matthew99 | 138 |

10 | PikMike | 137 |

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

↑

↓

Codeforces (c) Copyright 2010-2018 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: Jun/18/2018 00:54:13 (d3).

Desktop version, switch to mobile version.

User lists

Name |
---|

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/

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.

please describe any of them....

How do you do the "easy" part in less than O(N)? :)

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.

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

You can try this (not exactly same but similar): https://codeforces.com/contest/814/problem/D

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.