Вот обманчиво сложная геометрическая головоломка для вас!

Учитывая круг Aи nдругие круги B[n], найти общую площадь , содержащуюся в Aтом , что это не в пределах любого круга B.

Ваш код должен быть максимально коротким.

вход

Ваш вклад должен содержать следующую информацию:

• Число с плавающей точкой для представления радиуса круга A.
• Список чисел с плавающей точкой для представления радиусов окружностей в B.
• Список центров кругов в России B. Ваша программа может ожидать центры в полярных или декартовых координатах.
• При желании вы можете получить количество nкружков в B. Этот ввод не требуется.

Предполагается, что центром круга Aявляется начало координат, то есть точка (0, 0).

Гарантируется, что нет двух Bодинаковых окружностей , но не гарантируется, что: все окружности Bпересекаются A, все центры Bнаходятся снаружи Aили никакие две окружности не Bпересекаются друг с другом. Убедитесь, что ваше решение может обрабатывать различные крайние случаи.

Вы можете получать ввод в любом порядке и в форме ввода текста (через stdin или эквивалент вашего языка), параметров функции или аргументов командной строки.

Если вы решите получать ввод текста, между кусками ввода должен быть один или двухсимвольный печатаемый разделитель ASCII.

Выход

Ваша программа или функция должна вывести одно число с плавающей запятой, представляющее общую площадь Aвне любого круга B. Ваши ответы должны быть точными как минимум до трех значащих цифр для всех тестовых случаев.

Применяются общие правила игры в гольф .

Ваше решение не должно полагаться на точки отбора проб в кругах для определения области.

Встроенные модули, которые автоматически обнаруживают пересечения окружностей, находят области внутри пересечений окружностей или немедленно решают эту проблему, не допускаются.

Тестовые случаи

На каждом изображении круг Aобведен синим, а круги Bобведены зеленым и закрашены черным. Область, которая должна быть возвращена, заполнена красным.

(Отдельное спасибо Райнеру П. за проверку моих решений)

Тестовый пример 1:

A = {x: 0, y: 0, rad: 50}
B[0] = {x: 0, y: 0, rad: 100}

Result: 0.00

Контрольный пример 2:

A = {x: 0, y: 0, rad: 100.000000}
B[0] = {x: 100.000000, y: 0.000000, rad: 50.000000}
B[1] = {x: 30.901699, y: -95.105652, rad: 50.000000}
B[2] = {x: -80.901699, y: -58.778525, rad: 50.000000}
B[3] = {x: -80.901699, y: 58.778525, rad: 50.000000}
B[4] = {x: 30.901699, y: 95.105652, rad: 50.000000}

Result: 1.3878e+04

Тестовый пример 3:

A = {x: 0, y: 0, rad: 138}
B[0] = {x: 100, y: 0, rad: 100}
B[1] = {x: -50, y: -86, rad: 100} 
B[2] = {x: -93, y: 135, rad: 50}

Result: 1.8969e+04

Контрольный пример 4:

A = {x: 0, y: 0, rad: 121.593585}
B[0] = {x: 81.000000, y: 107.000000, rad: 59.841457}
B[1] = {x: -152.000000, y: -147.000000, rad: 50.000000}
B[2] = {x: 43.000000, y: -127.000000, rad: 105.118980}
B[3] = {x: 0.000000, y: -72.000000, rad: 57.870545}
B[4] = {x: -97.000000, y: -81.000000, rad: 98.488578}
B[5] = {x: -72.000000, y: 116.000000, rad: 66.468037}
B[6] = {x: 2.000000, y: 51.000000, rad: 50.000000}

Result: 1.1264e+04

Тестовый пример 5:

A = {x: 0, y: 0, rad: 121.605921}
B[0] = {x: 0.000000, y: -293.000000, rad: 250.000000}
B[1] = {x: 0.000000, y: -56.000000, rad: 78.230429}
B[2] = {x: 0.000000, y: -102.000000, rad: 100.000000}

Result: 2.6742e+04

Предлагаемое чтение:

Фьюэлл, М.П. «Область общего перекрытия трех кругов». Октябрь 2006 г. Интернет. http://dspace.dsto.defence.gov.au/dspace/bitstream/1947/4551/4/DSTO-TN-0722.PR.pdf .

Python 2, 631 байт

from cmath import*
C=input()
O,R=C[0]
def I(p,r,q,s):
 try:q-=p;d=abs(q*q);x=(r*r-s*s+d)/d/2;return[p+q*(x+z*(r*r/d-x*x)**.5)for z in-1j,1j]
 except:return[]
S=sorted
V=S(i.real for p,r in C for c in C for i in[p-r,p+r]+I(p,r,*c)if-R<=(i-O).real<=R)
A=pi*R*R
for l,r in zip(V,V[1:]):
 H=[]
 for p,t in C:
    try:
     for s in-1,1:a,b=[p.imag+s*(t*t-(p.real-x)**2)**.5for x in l,r];H+=[a+b,a,b,s,t,p],
    except:0
 a,b=H[:2];H=S(H[2:]);n=0;c=a
 for d in H:
    s=d[3];z=.5;H*=d<b
    for q,w,e,_,t,y in(c,min(d,b))*(n-s<(a<d)or[0]*n>H):\
g=phase((l+w*1j-y)/(r+e*1j-y));A-=abs(g-sin(g)).real*t*t/2-z*q*(r-l);z=-z
    n-=s
    if(a<d)*s*n==-1:c=d
print A

^{Разрывы строки, начинающиеся с, \предназначены для легкого чтения и не учитываются в счете.}

Читает ввод через STDIN в виде списка (center, radius)пар, гдеcenter в форме находится комплексное число X+Yj. Первый круг в списке (центр которого не должно быть в начале координат), а остальная часть списка B . Печатает результат в STDOUT.

пример

Input:  (0+0j, 138),  (100+0j, 100), (-50+-86j, 100), (-93+135j, 50)
Output: 18969.6900901

объяснение

Это (длиннее и гораздо страшнее: P) вариант моего решения задачи Области самопересекающегося многоугольника Мартина Бюттнера . Он использует тот же трюк, разбивая проблему на достаточно мелкие кусочки, для чего он становится более управляемым.

Мы находим точки пересечения между всеми парами окружностей (учитывая как A , так и окружности в B ) и пропускаем вертикальную линию через каждую из них. Кроме того, мы передаем все вертикальные линии, касающиеся любой из окружностей. Мы отбрасываем все линии, которые не пересекаются с A , так что все оставшиеся линии находятся между левой и правой касательными A .

Мы ищем область пересечения А и объединения кругов в B - темно-красную область на иллюстрации выше. Это та область, которую мы должны вычесть из A, чтобы получить результат.

Между каждой парой последовательных вертикальных линий эта область может быть разбита на набор вертикальных трапеций (или треугольников, или сегментов линий, как особые случаи трапеций) с «избыточным» сегментом дуги рядом с каждой ногой. Тот факт, что мы пропускаем столько вертикальных линий, сколько и делаем, гарантирует, что ограниченная область действительно не сложнее, чем это, поскольку в противном случае должна была бы быть дополнительная точка пересечения и, следовательно, дополнительная вертикальная линия между двумя линиями в вопрос.

Чтобы найти эти трапеции и сегменты дуг, для каждой пары последовательных вертикальных линий мы найдем сегменты дуг каждого из кругов, которые должным образом лежат между этими двумя линиями (конечно, некоторые круги могут не иметь сегмента дуги между данной парой линий .) На рисунке ниже показаны шесть (ярких и темных) желтых дуговых сегментов, если учитывать две красные вертикальные линии. Обратите внимание, что, поскольку мы пропускаем все вертикальные линии, касательные к окружностям, если у окружности есть сегмент дуги между двумя линиями, он обязательно пересекает обе линии, что упрощает остальную часть алгоритма.

Не все эти дуги актуальны; мы заинтересованы только в тех , которые находятся на границе пересечения между А и объединение B . Чтобы найти их, мы сортируем дуги сверху вниз (обратите внимание, что дуги могут неправильно пересекаться друг с другом, так как это подразумевает существование другой вертикальной линии между двумя рассматриваемыми нами, и поэтому имеет смысл говорить о произвольной дуге, находящейся выше или ниже любой другой.)

Мы пересекаем дуги по порядку, сохраняя при этом количество кругов B, в которых мы сейчас находимся, n . Если n изменяется от 0 до 1, пока мы находимся внутри A , или если мы находимся на верхней дуге A, когда n отлично от нуля, то текущая дуга соответствует одной ветви трапеции. Если n изменяется от 1 до 0, пока мы находимся внутри А , или если мы находимся на нижней дуге А, пока nотлична от нуля, тогда текущая дуга соответствует другой ветви той же трапеции. Как только мы находим такую ​​пару дуг (две ярко-желтые дуги на рисунке выше), мы рассчитываем площадь соответствующей трапеции и двух дуговых сегментов и добавляем ее к общей площади, которую нужно вычесть из A .

Расчет площади A , а также площадей трапеций, довольно прост. Площадь каждого сегмента дуги - это площадь соответствующего кругового сектора, за вычетом площади треугольника, вершинами которого являются две конечные точки сегмента дуги, и центром соответствующего круга.