Encuentra el área de un polígono

9

Dadas las longitudes laterales consecutivas s1, s2, s3... s_nde un n-gon inscrito en un círculo, encuentre su área. Puede suponer que el polígono existe. Además, el polígono será convexo y no se intersectará a sí mismo, lo que es suficiente para garantizar la unicidad. Las funciones integradas que resuelven específicamente este desafío, así como las funciones integradas que calculan el circunradio o el circuncentro, están prohibidas (esto es diferente de una versión anterior de este desafío).

Entrada: las longitudes laterales del polígono cíclico; se pueden tomar como parámetros de una función, stdin, etc.

Salida: el área del polígono.

La respuesta debe tener una precisión de 6 decimales y debe ejecutarse en 20 segundos en una computadora portátil razonable.

Este es el código de golf, ¡el código más corto gana!

Casos de prueba específicos:

[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

Generador de casos de prueba:

soktinpk
fuente
77
Sé una manera fácil de encontrar su perímetro.
mIllIbyte
1
Sé una manera fácil de encontrar el número de lados
Luis Mendo
Este problema es bastante fácil dado el circunradio, pero sin él es increíblemente difícil.
poi830
También es fácil si hay menos de cinco lados, no es que importe en el golf de código.
Neil

Respuestas:

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

Utiliza una búsqueda binaria para encontrar el radio, luego calcula el área de cada segmento por el ángulo / radio.

Encuentra el radio al sumar primero todos los ángulos de acorde menos el más grande y verificar el ángulo restante con el acorde restante. Esos ángulos también se usan para calcular el área de cada segmento. El área de un segmento puede ser negativa, si su ángulo es mayor de 180 grados.

Implementación legible:

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
fuente
¿Funciona esto si el centro está fuera del polígono? (Por ejemplo, un triángulo con lados de longitud 6, 7, 12). A veces, la sqrt(4**2 - c**2/4)necesidad debe ser negativa, cuando el ángulo es mayor que pi.
soktinpk
@soktinpk Arregle mi respuesta.
orlp
0

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

Explicación

El ángulo que aabarca un segmento de longitud ses 2*asin(s/2/r), dado un circunradio r. Su área es cos(a)*s/2*r.

Algoritmo

  1. Establezca ralgo demasiado grande, como el perímetro.
  2. Si el ángulo acumulado es menor que 2pi, reduzca ry repita el paso 2.
  3. Calcule el área.
Rainer P.
fuente
En promedio, ¿cuántas iteraciones tarda esto ren establecerse? (por curiosidad)
soktinpk
No hay forma de que esto tenga la precisión requerida. Multiplica repetidamente el radio por 0.9999 para reducirlo, esto hace que sea muy fácil superar los 6 decimales de precisión requeridos.
orlp
@soktinpk alrededor de 15000 para r*=1-1e-4y 150000 para r*=1-1e-5.
Rainer P.
@RainerP. Esos dos valores son iguales.
Fondo de la demanda de Mónica
1
@soktinpk generalmente no es una buena idea hacer una excepción para una respuesta específica.
Cyoce