Given multiple 2D points and circles, find all points that are enclosed by a chain of circles?

Правка en3, от pabloskimg, 2018-10-13 22:15:15

Given a lot of points and circles, you have to find all points that are either inside a circle or surrounded by a closed loop of circles (a sequence of circles of some length N such that circle i intersects circle (i+1)%N). For example, in the picture below, all red points would be points satisfying the aforementioned condition:

I need to figure this out in order to solve this problem. UPDATE: solutions can be submitted here: http://poj.org/problem?id=2863, if you solve it, please let me know which strategy you used :D

I guess I need to build a graph where circles are nodes and add edges between circles intersecting each other. Then I would have to find somehow maximal cycles in this graph, for each maximal cycle find the corresponding maximal polygon formed by connecting the centers of circles in the maximal cycle with segments in counter-clockwise order, and finally for each point check if it's contained by one of these maximal polygons. I've got no idea of how to do anything of this :(

#### История

Правки

Rev. Язык Кто Когда Δ Комментарий
en3 pabloskimg 2018-10-13 22:15:15 137
en2 pabloskimg 2018-10-12 00:43:10 9
en1 pabloskimg 2018-09-29 20:27:31 1120 Initial revision (published)