Dadas las longitudes laterales consecutivas s1, s2, s3... s_n
de 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:
function randPolygon(n) {
var left = 2 * Math.PI;
var angles = [];
for (var i = 0; i < n - 1; ++i) {
var r = Math.random() * left;
angles.push(r);
left -= r;
}
angles.push(left);
var area = 0;
var radius = 1 + Math.random() * 9;
for (var i = 0; i < angles.length; ++i) area += radius * radius * Math.sin(angles[i]) / 2;
var sideLens = angles.map(function(a) {
return Math.sin(a / 2) * radius * 2;
});
document.querySelector("#radius").innerHTML = radius;
document.querySelector("#angles").innerHTML = "[" + angles.join(", ") + "]";
document.querySelector("#inp").innerHTML = "[" + sideLens.join(", ") + "]";
document.querySelector("#out").innerHTML = area;
draw(angles);
}
function draw(angles) {
var canv = document.querySelector("#diagram"),
ctx = canv.getContext("2d");
var size = canv.width
ctx.clearRect(0, 0, size, size);
ctx.beginPath();
ctx.arc(size / 2, size / 2, size / 2, 0, 2 * Math.PI, true);
ctx.stroke();
ctx.beginPath();
ctx.moveTo(size, size / 2);
var runningTotal = 0;
for (var i = 0; i < angles.length; ++i) {
runningTotal += angles[i];
var x = Math.cos(runningTotal) * size / 2 + size / 2;
var y = Math.sin(runningTotal) * size / 2 + size / 2;
ctx.lineTo(x, y);
}
ctx.stroke();
}
document.querySelector("#gen").onclick = function() {
randPolygon(parseInt(document.querySelector("#sideLens").value, 10));
}
<div id="hints">
<p><strong>These are to help you; they are not part of the input or output.</strong>
</p>
Circumradius:
<pre id="radius"></pre>
Angles, in radians, of each sector (this are NOT the angles of the polygon):
<pre id="angles"></pre>
</div>
<hr>
<div id="output">
Input:
<pre id="inp"></pre>
Output:
<pre id="out"></pre>
</div>
<hr>
<div id="draw">
Diagram:
<br />
<canvas id="diagram" width="200" height="200" style="border:1px solid black"></canvas>
</div>
Number of side lengths:
<input type="number" id="sideLens" step="1" min="3" value="3" />
<br />
<button id="gen">Generate test case</button>
Respuestas:
Python 2, 191 bytes
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:
fuente
sqrt(4**2 - c**2/4)
necesidad debe ser negativa, cuando el ángulo es mayor quepi
.Octava, 89 bytes
Explicación
El ángulo que
a
abarca un segmento de longituds
es2*asin(s/2/r)
, dado un circunradior
. Su área escos(a)*s/2*r
.Algoritmo
r
algo demasiado grande, como el perímetro.2pi
, reduzcar
y repita el paso 2.fuente
r
en establecerse? (por curiosidad)r*=1-1e-4
y 150000 parar*=1-1e-5
.