Trouver l'aire d'un polygone

9

Étant donné les longueurs latérales consécutives s1, s2, s3... s_nd'un n-gon inscrit dans un cercle, trouvez son aire. Vous pouvez supposer que le polygone existe. De plus, le polygone sera convexe et non auto-intersecté, ce qui est suffisant pour garantir l'unicité. Les fonctions intégrées qui résolvent spécifiquement ce défi, ainsi que les fonctions intégrées qui calculent le circumradius ou le circumcenter, sont interdites (ce qui est différent d'une version précédente de ce défi).

Entrée: les longueurs latérales du polygone cyclique; peut être pris comme paramètre d'une fonction, stdin, etc.

Sortie: l'aire du polygone.

La réponse doit être précise à 6 décimales et doit s'exécuter dans les 20 secondes sur un ordinateur portable raisonnable.

C'est le golf de code donc le code le plus court gagne!

Cas de test spécifiques:

[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

Générateur de cas de test:

soktinpk
la source
7
Je connais un moyen facile de trouver son périmètre.
mIllIbyte
1
Je connais un moyen facile de trouver le nombre de côtés
Luis Mendo
Ce problème est assez facile compte tenu du circumradius, mais sans lui, c'est incroyablement difficile.
poi830
C'est aussi facile s'il y a moins de cinq côtés, ce n'est pas important dans le golf de code.
Neil

Réponses:

5

Python 2, 191 octets

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

Utilise une recherche binaire pour trouver le rayon, puis calcule l'aire de chaque segment par l'angle / rayon.

Il trouve le rayon en additionnant tout d'abord, sauf le plus grand angle d'accord, et en vérifiant l'angle restant par rapport à l'accord restant. Ces angles sont ensuite également utilisés pour calculer l'aire de chaque segment. La zone d'un segment peut être négative si son angle est supérieur à 180 degrés.

Implémentation lisible:

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
la source
Est-ce que cela fonctionne si le centre est en dehors du polygone? (Par exemple, un triangle dont les côtés mesurent 6, 7, 12). Parfois, le sqrt(4**2 - c**2/4)besoin doit être négatif, lorsque l'angle est supérieur à pi.
soktinpk
@soktinpk J'ai corrigé ma réponse.
orlp
0

Octave, 89 octets

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))

Explication

L'angle acouvert par un segment de longueur sest 2*asin(s/2/r), étant donné un circumradius r. Sa zone est cos(a)*s/2*r.

Algorithme

  1. Définissez rsur quelque chose de trop grand, comme le périmètre.
  2. Si l'angle cumulé est inférieur à 2pi, réduisez ret répétez l'étape 2.
  3. Calculez la surface.
Rainer P.
la source
En moyenne, combien d'itérations cela prend-il pour rêtre défini? (par curiosité)
soktinpk
Il n'y a aucun moyen que cela ait la précision requise. Vous multipliez à plusieurs reprises le rayon par 0,9999 pour le réduire, ce qui rend très facile le sous-dépassement des 6 décimales de précision requises.
orlp
@soktinpk autour de 15000 pour r*=1-1e-4et 150000 pour r*=1-1e-5.
Rainer P.
@RainerP. Ces deux valeurs sont les mêmes.
Fund Monica's Lawsuit
1
@soktinpk ce n'est généralement pas une bonne idée de faire une exception pour une réponse spécifique.
Cyoce