русский
english
Как можно решить эту задачу?
Вы не подписаны на эту тему. Подписаться
|
mansur115 | 2012-02-17 16:06:16 Пришел к выводу что можно составить граф, в котором вершины это наши окружности, а ребра проведены между теми окружностями, которые пересекаются в 2 точках. Ответом будет количество клик в этом графе. Но это кажется ужасным. Есть ли алгоритм попроще? |
|
Здесь можно делать так: построить граф, где вершинами будут точки пересечения окружностей, а рёбрами - дуги окружностей, после чего применить к нему формулу Эйлера для планарных графов \(V+G-E=1+C\), где \(V\) - количество вершин, \(E\) - рёбер, \(C\) - компонент связности, а \(G\) - граней (как раз тех частей, которые нам требуется найти. Правда задача не без приколов - надо аккуратно учесть окружности, не пересекающиеся ни с чем (с точки зрения графа это 1 вершина, одно ребро и одна компонента связности. Ну и надо аккуратно с тем, когда несколько окружностей пересекаются в одной точке - точки на равенство сравнивать при помощи eps. Редактировано 2012-02-17 21:57:34. |
Версия для печати