|
Название задачи: Пересечение окружностей . |
 |
Условие
На плоскости провели N окружностей. Требуется определить площадь их пересечения.Входные данные
В первой строке входного файла находится целое число N (1 ≤ N ≤ 20). В каждой из последующих N строк записана тройка вещественных чисел, описывающих очередную из окружностей. Первые два числа задают координаты ее центра, третье – радиус.
Выходные данные
Выведите в выходной файл искомую площадь не менее чем с 6 верными значащими цифрами.
Пример входного файла
2
0 0 1
1 1 1
Пример выходного файла
0.570796
Решение
Скачать архив тестов и решенийПересечением нескольких окружностей является выпуклая фигура, которую можно представить как многоугольник и сегменты, примыкающие к его сторонам. Это разбиение на многоугольник и сегменты не является единственным, поскольку любой сегмент можно разбить на треугольник и два новых сегмента (см. рис.).
Приступим к решению. Вначале найдем точки пересечения всех пар окружностей. Если точка пересечения двух окружностей принадлежит всем остальным, то она является вершиной интересующего нас многоугольника. Получив все такие вершины, упорядочим их сортировкой по полярному углу относительно центра масс.
По построенному многоугольнику, «вписанному» в пересечение, в некоторых случаях уже можно посчитать искомую площадь. Действительно, каждая его сторона является хордой некоторой окружности (обратитесь к рис.). Сложив суммарную площадь всех соответствующих сегментов этих окружностей с площадью многоугольника, получим ответ. Однако в других случаях при этом возникнут проблемы. Во-первых, точек, являющихся его вершинами, может не оказаться вовсе, либо найдется только одна его вершина, а пересечение при этом будет непустым. (Рассмотрите случаи, когда одна окружность вложена в другую или они касаются внутренним образом.) Во-вторых, в случае, например, пересечения только двух окружностей многоугольник вырождается в отрезок, являющийся хордой сразу обеих этих окружностей. При попытке подсчета площади прилегающего к нему сегмента не совсем ясно, какой из сегментов и какой из окружностей следует выбрать.
Для решения всех перечисленных проблем предлагается выполнить следующее построение. Для каждой пары окружностей найдем точки пересечения прямой, проходящей через их центры, с самими окружностями (если мы встретим две концентрические окружности, то внешнюю из них нужно отбросить). Из этих точек выберем только те, которые принадлежат всем окружностям, и добавим их к списку вершин нашего многоугольника. В результате добавления этих вершин для любой стороны многоугольника (возможно вырожденного) сегмент, прилегающий к ней, будет определяться однозначно, так как соседние вершины всегда будут лежать на какой-то одной окружности, а из двух сегментов этой окружности всегда нужно выбирать наименьший.
