Oto zwodniczo trudna łamigłówka geometrii dla Ciebie!

Biorąc pod uwagę krąg Ai ninne kręgi B[n], znajdź całkowity obszar w nim zawarty, Aktóry nie znajduje się w żadnym kręgu B.

Twój kod powinien być jak najkrótszy.

Wejście

Twój wkład powinien zawierać następujące informacje:

• Liczba zmiennoprzecinkowa reprezentująca promień okręgu A.
• Lista liczb zmiennoprzecinkowych reprezentujących promienie okręgów B.
• Lista centrów kół w B. Twój program może oczekiwać centrów we współrzędnych biegunowych lub kartezjańskich.
• Opcjonalnie możesz otrzymać liczbę nkręgów w B. To wejście nie jest wymagane.

Należy założyć, że środek koła Ajest początkiem, to znaczy punktem (0, 0).

To jest zagwarantowane, że żadne dwa okręgi Bsą identyczne, ale to nie gwarantuje, że: wszystkie okręgi Bprzecinają się A, wszystkie ośrodki Bsą na zewnątrz A, a nie dwa okręgiB przecinają się nawzajem. Upewnij się, że Twoje rozwiązanie obsługuje różne przypadki brzegowe.

Możesz otrzymywać dane wejściowe w dowolnej kolejności, w formie wprowadzania tekstu (przez stdin lub odpowiednik twojego języka), parametrów funkcji lub argumentów wiersza poleceń.

Jeśli zdecydujesz się na wprowadzanie tekstu, pomiędzy fragmentami tekstu powinien znajdować się jeden lub dwa znaki ograniczające ASCII.

Wynik

Twój program lub funkcja powinna wypisać pojedynczą liczbę zmiennoprzecinkową reprezentującą całkowity obszar Aspoza żadnego z okręgówB . Twoje odpowiedzi powinny być zgodne z co najmniej trzema znaczącymi liczbami dla wszystkich przypadków testowych.

Obowiązują ogólne zasady gry w golfa .

Twoje rozwiązanie nie powinno opierać się na punktach próbkowania w okręgach, aby określić obszar.

Wbudowane funkcje, które automatycznie lokalizują przecięcia okręgów, znajdują obszary w przecięciach okręgów lub natychmiast rozwiązują ten problem, są niedozwolone.

Przypadki testowe

Na każdym zdjęciu koło Ajest obrysowane na niebiesko, a koła Bna zielono i wypełnione czernią. Obszar, który należy zwrócić, jest wypełniony na czerwono.

(Specjalne podziękowania dla Rainera P. za sprawdzenie moich rozwiązań)

Przypadek testowy 1:

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

Result: 0.00

Przypadek testowy 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

Przypadek testowy 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

Przypadek testowy 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

Przypadek testowy 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

Sugerowane czytanie:

Fewell, MP „Obszar wspólnego nakładania się trzech kół”. Październik 2006. Internet. http://dspace.dsto.defence.gov.au/dspace/bitstream/1947/4551/4/DSTO-TN-0722.PR.pdf .

Python 2, 631 bajtów

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

^{Podziały linii poprzedzone przez \ są dla łatwego czytania i nie są liczone w wyniku.}

Czyta dane wejściowe przez STDIN jako listę (center, radius)par, gdzie centerjest liczbą zespoloną w formularzu X+Yj. Pierwszym okręgiem na liście jest A (którego środek nie musi znajdować się na początku), a reszta listy to B . Drukuje wynik do STDOUT.

Przykład

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

Wyjaśnienie

Jest to (dłuższa i o wiele bardziej brzydsza: P) odmiana mojego rozwiązania problemu Martin Büttner's Area of ​​Self-przecinającego się wielokąta . Wykorzystuje tę samą sztuczkę, dzieląc problem na wystarczająco małe części, dzięki czemu staje się łatwiejszy do opanowania.

Znajdujemy punkty przecięcia między wszystkimi parami kół (biorąc pod uwagę zarówno A , jak i koła w B ) i przechodzimy przez każdą z nich pionową linię. Dodatkowo przekazujemy wszystkie linie pionowe styczne do dowolnego z okręgów. Wyrzucamy wszystkie linie, które nie przecinają A , tak, że wszystkie pozostałe linie są między lewą i prawą stycznych A .

Szukamy obszaru przecięcia A i połączenia kręgów w B - ciemnoczerwonego obszaru na powyższej ilustracji. Jest to obszar, który musimy odjąć od A, aby uzyskać wynik.

Pomiędzy każdą parą kolejnych pionowych linii obszar ten można podzielić na zestaw pionowych trapezoidów (lub trójkątów lub odcinków linii, jako specjalne przypadki trapezoidów), z „nadmiarowym” segmentem łukowym obok każdej nogi. Fakt, że mijamy tyle linii pionowych, ile robimy, gwarantuje, że obszar ograniczony nie jest wcale bardziej skomplikowany, ponieważ w przeciwnym razie musiałby istnieć dodatkowy punkt przecięcia, a zatem dodatkowa linia pionowa, między dwiema liniami w pytanie.

Aby znaleźć te trapezoidy i segmenty łuku, dla każdej pary kolejnych linii pionowych znajdujemy segmenty łuku każdego z okręgów, które prawidłowo leżą między tymi dwiema liniami (oczywiście niektóre koła mogą nie mieć segmentu łuku między daną parą linii .) Na poniższej ilustracji są to sześć (jasne i ciemne) żółte segmenty łuku, biorąc pod uwagę dwie czerwone pionowe linie. Zauważ, że ponieważ mijamy wszystkie linie pionowe styczne do okręgów, jeśli okrąg ma segment łukowy między dwiema liniami, to koniecznie przecina obie linie, co upraszcza resztę algorytmu.

Nie wszystkie z tych łuków są istotne; jesteśmy zainteresowani tylko w tych, które są na granicy styku A i związek B . Aby je znaleźć, sortujemy łuki od góry do dołu (zwróć uwagę, że łuki mogą nie przecinać się prawidłowo, ponieważ oznaczałoby to istnienie innej linii pionowej między dwoma, które rozważamy, i dlatego warto rozmawiać o tym, że dowolny łuk znajduje się powyżej lub poniżej dowolnego innego).

Przemierzamy łuki w kolejności, zachowując liczbę kręgów B , w których aktualnie jesteśmy, n . Jeśli n zmieni się z 0 na 1, gdy jesteśmy w środku A , lub jeśli znajdujemy się na górnym łuku A, gdy n jest niezerowe, to bieżący łuk odpowiada jednej odnodze trapezu. Jeśli n zmieni się z 1 na 0, gdy jesteśmy w środku A , lub jeśli znajdujemy się na dolnym łuku A, gdy njest niezerowe, wówczas bieżący łuk odpowiada drugiej odnodze tego samego trapezu. Gdy znajdziemy taką parę łuków (dwa jaskrawo żółte łuki na powyższej ilustracji), obliczamy obszar odpowiedniego trapezu i dwóch segmentów łukowych i dodajemy go do całkowitego pola do odjęcia od A .

Obliczanie obszaru A , a także obszarów trapezoidów, jest dość proste. Obszar każdego segmentu łuku jest obszarem odpowiedniego sektora kołowego, minus obszar trójkąta, którego wierzchołki są dwoma punktami końcowymi segmentu łuku, i środkiem odpowiedniego koła.