Площадь пересечения двух кругов

Даны координаты центров двух окружностей (X1, Y1) и (X2, Y2), а также радиусы соответствующих окружностей R1 и R2. Найдите пол площади их пересечения.

Примечание . Используйте значение числа Пи как 3,14.

Примеры :

Input: X1 = 0, Y1 = 0, R1 = 4, X2 = 6, Y2 = 0, R2 = 4
Output: 7
Explanation: The intersecting area equals 7.25298806. So, Answer is 7.

Input: X1 = 0, Y1 = 0, R1 = 5, X2 = 11, Y2 = 0, R2 = 5
Output: 0
Explanation: The circles don’t intersect.

Подход: выполните шаги, чтобы решить эту проблему:

• Сначала вычислите евклидово расстояние между двумя точками и сохраните его (скажем, d ).
• Если d > R1 + R2 , то круг никогда не бывает насекомым, поэтому верните 0.
• В противном случае, если d ≤ (R1 – R2) и R1 ≥ R2 , то окружность с радиусом R2 находится внутри окружности с радиусом R1 , поэтому возвращаем пол (Pi * R2 * R2).
• В противном случае, если d ≤ (R2 – R1) и R2 ≥ R1 , то окружность с радиусом R1 находится внутри окружности с радиусом R2 , поэтому возвращаем пол (Pi * R1 * R1).
• В противном случае найдите:
  • альфа = acos((R1 * R1 + d * d – R2 * R2) / (2 * R1 * d)) * 2 [acos — арккосинус]
  • бета = acos((R2 * R2 + d * d – R1 * R1) / (2 * R2 * d)) * 2
  • a1 = 0,5 * бета * R2 * R2 - 0,5 * R2 * R2 * sin (бета)
  • a2 = 0,5 * альфа * R1 * R1 - 0,5 * R1 * R1 * грех (альфа)
  • Возвратите значение floor(a1+a2) .

Ниже приведена реализация описанного выше подхода.

Временная сложность : O (log N)
Вспомогательное пространство : O(1)