Suchen Sie den Bereich eines Polygons

9

Bestimmen Sie bei aufeinanderfolgenden Seitenlängen s1, s2, s3... s_neines in einen Kreis eingeschriebenen n-Gons dessen Fläche. Sie können davon ausgehen, dass das Polygon vorhanden ist. Darüber hinaus ist das Polygon konvex und schneidet sich nicht selbst, was ausreicht, um die Eindeutigkeit zu gewährleisten. Integrierte Funktionen, die diese Herausforderung speziell lösen, sowie integrierte Funktionen zur Berechnung des Zirkumradius oder des Zirkumzentrums sind verboten (dies unterscheidet sich von einer früheren Version dieser Herausforderung).

Eingabe: Die Seitenlängen des zyklischen Polygons; kann als Parameter für eine Funktion, ein Standard usw. verwendet werden.

Ausgabe: Die Fläche des Polygons.

Die Antwort sollte auf 6 Dezimalstellen genau sein und innerhalb von 20 Sekunden auf einem vernünftigen Laptop ausgeführt werden.

Dies ist Code Golf, also gewinnt der kürzeste Code!

Spezifische Testfälle:

[3, 4, 5] --> 6
[3, 4, 6] --> 5.332682251925386
[3, 4, 6, 7] --> 22.44994432064365
[5, 5, 5, 5] --> 25
[6, 6, 6, 6, 6] --> 61.93718642120281
[6.974973020933265, 2.2393294197257387, 5.158285083300981, 1.4845682771595603, 3.5957940796134173] --> 21.958390804292847
[7.353566082457831, 12.271766915518073, 8.453884922273897, 9.879017670784675, 9.493366404245332, 1.2050010402321778] --> 162.27641678140589

Testfallgenerator:

soktinpk
quelle
7
Ich kenne einen einfachen Weg, um seinen Umfang zu finden.
mIllIbyte
1
Ich kenne einen einfachen Weg, um die Anzahl der Seiten zu finden
Luis Mendo
Dieses Problem ist angesichts des Zirkumradius ziemlich einfach, aber ohne es ist es unglaublich schwierig.
Poi830
Es ist auch einfach, wenn es weniger als fünf Seiten gibt, nicht dass es beim Code-Golf wichtig ist.
Neil

Antworten:

5

Python 2, 191 Bytes

from math import*
C=sorted(input());l,h=C[-1]/2,sum(C)
while h-l>1e-9:m=l+h;a=[asin(c/m)for c in C[:-1]];f=pi-sum(a);l,h=[l,m/2,h][m*sin(f)<C[-1]:][:2]
print sum(l*l*sin(2*t)for t in a+[f])/2

Verwendet eine binäre Suche, um den Radius zu finden, und berechnet dann die Fläche jedes Segments anhand des Winkels / Radius.

Der Radius wird ermittelt, indem zuerst alle bis auf den größten Akkordwinkel summiert und der verbleibende Winkel zum verbleibenden Akkord überprüft wird. Diese Winkel werden dann auch verwendet, um die Fläche jedes Segments zu berechnen. Die Fläche eines Segments kann negativ sein, wenn sein Winkel größer als 180 Grad ist.

Lesbare Implementierung:

import math

def segment_angles(line_segments, r):
    return [2*math.asin(c/(2*r)) for c in line_segments]

def cyclic_ngon_area(line_segments):
    line_segments = list(sorted(line_segments))
    lo, hi = max(line_segments) / 2, sum(line_segments)
    while hi - lo > 1e-9:
        mid = (lo + hi) / 2
        angles = segment_angles(line_segments[:-1], mid)
        angles.append(2*math.pi - sum(angles))
        if 2 * mid * math.sin(angles[-1]/2) < line_segments[-1]:
            lo = mid
        else:
            hi = mid
    return sum([lo*lo * math.sin(a) / 2 for a in angles])
orlp
quelle
Funktioniert dies, wenn sich die Mitte außerhalb des Polygons befindet? (Zum Beispiel ein Dreieck mit den Seitenlängen 6, 7, 12). Manchmal sqrt(4**2 - c**2/4)muss das negativ sein, wenn der Winkel größer als ist pi.
Saktinpk
@soktinpk Ich habe meine Antwort korrigiert.
Orlp
0

Oktave, 89 Bytes

r=sum(s=input(''));while sum(a=asin(s/2/r))<pi r*=1-1e-4;b=a;end;disp(sum(cos(b).*s/2*r))

Erläuterung

Der Winkel adurch ein Segment der Länge aufgespannt swird 2*asin(s/2/r), einen circumradius gegeben r. Seine Fläche ist cos(a)*s/2*r.

Algorithmus

  1. Stellen Sie retwas zu Großes ein, z. B. den Umfang.
  2. Wenn der kumulierte Winkel kleiner als ist 2pi, reduzieren Sie rSchritt 2 und wiederholen Sie ihn.
  3. Berechnen Sie die Fläche.
Rainer P.
quelle
Wie viele Iterationen dauert es durchschnittlich, rbis diese festgelegt sind? (aus Neugier)
soktinpk
Dies hat auf keinen Fall die erforderliche Präzision. Sie multiplizieren den Radius wiederholt mit 0,9999, um ihn zu verringern. Dadurch ist es sehr einfach, die erforderlichen 6 Dezimalstellen zu unterschreiten.
Orlp
@soktinpk um 15000 für r*=1-1e-4und 150000 für r*=1-1e-5.
Rainer P.
@RainerP. Diese beiden Werte sind gleich.
Fund Monica Klage
1
@soktinpk Es ist im Allgemeinen keine gute Idee, eine Ausnahme für eine bestimmte Antwort zu machen.
Cyoce