Lado mínimo de un cuadrado incrustado en un polígono regular de N lados

Dado un número par N que representa el número de lados de un polígono regular con N vértices, la tarea es encontrar el cuadrado del tamaño mínimo tal que el polígono dado pueda incrustarse completamente en el cuadrado. 
 

Un polígono es una figura convexa y tiene lados y ángulos iguales. Todos los lados tienen longitud 1 .

Incrustación: coloque el polígono en el cuadrado de tal manera que cada punto que se encuentra dentro o en un borde de N también debe estar dentro o en un borde del cuadrado.
Ejemplos: 
 

Entrada: N = 4 
Salida:
Explicación: 
El polígono regular de 4 lados es un cuadrado de lado 1. El 
polígono dado se puede incrustar fácilmente en el cuadrado de lado 1. 
Entrada: N = 6 
Salida: 1,931851653 
Explicación: 
El polígono regular de 6 lados es un hexágono con lado 1. 
El polígono dado puede incrustarse fácilmente en el cuadrado con lado 1.931851653. 
 

Enfoque: La idea es observar que en un plano tridimensional, cuando un polígono está incrustado en un cuadrado, podría girarse. Se ha discutido un enfoque similar en el Problema del hexágono y el Problema del octágono . Por lo tanto, tomamos la proyección de cada lado en ambos ejes usando las funciones matemáticas sin() y cos() . La suma total de todas las proyecciones es el lado mínimo del cuadrado requerido en este problema. 
A continuación se muestra la implementación del enfoque anterior: 
 

C++

// C++ program to find the minimum
// side of the square in which
// a regular polygon with even sides
// can completely embed
 
#include <bits/stdc++.h>
using namespace std;
 
// PI value in C++ using
// acos function
const double pi = acos(-1.0);
 
// Function to find the minimum
// side of the square in which
// a regular polygon with even sides
// can completely embed
double nGon(int N)
{
 
    // Projection angle variation
    // from axes
    double proAngleVar;
 
    // Projection angle variation
    // when the number of
    // sides are in multiple of 4
    if (N % 4 == 0) {
        proAngleVar
            = pi * (180.0 / N)
              / 180;
    }
    else {
        proAngleVar
            = pi * (180.0 / (2 * N))
              / 180;
    }
 
    // Distance between the end points
    double negX = 1.0e+99,
           posX = -1.0e+99,
           negY = 1.0e+99,
           posY = -1.0e+99;
 
    for (int j = 0; j < N; ++j) {
 
        // Projection from all N points
        // on X-axis
        double px = cos(2 * pi * j / N
                        + proAngleVar);
 
        // Projection from all N points
        // on Y-axis
        double py = sin(2 * pi * j / N
                        + proAngleVar);
 
        negX = min(negX, px);
        posX = max(posX, px);
        negY = min(negY, py);
        posY = max(posY, py);
    }
 
    // Maximum side
    double opt2 = max(posX - negX,
                      posY - negY);
 
    // Return the portion of side
    // forming the square
    return (double)opt2
           / sin(pi / N) / 2;
}
 
// Driver code
int main()
{
    int N = 10;
    cout << nGon(N);
    return 0;
}

Java

// Java program to find the minimum
// side of the square in which
// a regular polygon with even sides
// can completely embed
class GFG{
 
// PI value in Java using
// acos function
static double pi = Math.acos(-1.0);
 
// Function to find the minimum
// side of the square in which
// a regular polygon with even sides
// can completely embed
static double nGon(int N)
{
 
    // Projection angle variation
    // from axes
    double proAngleVar;
 
    // Projection angle variation
    // when the number of
    // sides are in multiple of 4
    if (N % 4 == 0)
    {
        proAngleVar = pi * (180.0 / N) / 180;
    }
    else
    {
        proAngleVar = pi * (180.0 / (2 * N)) / 180;
    }
 
    // Distance between the end points
    double negX = 1.0e+99,
           posX = -1.0e+99,
           negY = 1.0e+99,
           posY = -1.0e+99;
 
    for (int j = 0; j < N; ++j)
    {
 
        // Projection from all N points
        // on X-axis
        double px = Math.cos(2 * pi * j / N +
                                proAngleVar);
 
        // Projection from all N points
        // on Y-axis
        double py = Math.sin(2 * pi * j / N +
                                proAngleVar);
 
        negX = Math.min(negX, px);
        posX = Math.max(posX, px);
        negY = Math.min(negY, py);
        posY = Math.max(posY, py);
    }
 
    // Maximum side
    double opt2 = Math.max(posX - negX,
                           posY - negY);
 
    // Return the portion of side
    // forming the square
    return (double)opt2 /
            Math.sin(pi / N) / 2;
}
 
// Driver code
public static void main(String[] args)
{
    int N = 10;
    System.out.printf("%.5f",nGon(N));
}
}
 
// This code is contributed by 29AjayKumar

Python3

# Python 3 program to find the minimum
# side of the square in which
# a regular polygon with even sides
# can completely embed
import math
 
# PI value in Python 3 using
# acos function
pi = math.acos(-1.0)
 
# Function to find the minimum
# side of the square in which
# a regular polygon with even sides
# can completely embed
def nGon(N):
 
    # Projection angle variation
    # from axes
    proAngleVar = 0
 
    # Projection angle variation
    # when the number of
    # sides are in multiple of 4
    if (N % 4 == 0):
        proAngleVar = (pi * (180.0 / N)
                       / 180)
 
    else:
        proAngleVar = (pi * (180.0 / (2 * N))
                       / 180)
 
    # Distance between the end points
    negX = 1.0e+99
    posX = -1.0e+99
    negY = 1.0e+99
    posY = -1.0e+99
 
    for j in range(N):
 
        # Projection from all N points
        # on X-axis
        px = math.cos(2 * pi * j / N
                      + proAngleVar)
 
        # Projection from all N points
        # on Y-axis
        py = math.sin(2 * pi * j / N
                      + proAngleVar)
 
        negX = min(negX, px)
        posX = max(posX, px)
        negY = min(negY, py)
        posY = max(posY, py)
 
    # Maximum side
    opt2 = max(posX - negX,
               posY - negY)
 
    # Return the portion of side
    # forming the square
    return (opt2 / math.sin(pi / N) / 2)
 
# Driver code
if __name__ == "__main__":
 
    N = 10
    print('%.5f'%nGon(N))
 
    # This code is contributed by ukasp.

C#

// C# program to find the minimum
// side of the square in which
// a regular polygon with even sides
// can completely embed
using System;
class GFG{
 
// PI value in Java using
// acos function
static double pi = Math.Acos(-1.0);
 
// Function to find the minimum
// side of the square in which
// a regular polygon with even sides
// can completely embed
static double nGon(int N)
{
 
    // Projection angle variation
    // from axes
    double proAngleVar;
 
    // Projection angle variation
    // when the number of
    // sides are in multiple of 4
    if (N % 4 == 0)
    {
        proAngleVar = pi * (180.0 / N) / 180;
    }
    else
    {
        proAngleVar = pi * (180.0 / (2 * N)) / 180;
    }
 
    // Distance between the end points
    double negX = 1.0e+99,
           posX = -1.0e+99,
           negY = 1.0e+99,
           posY = -1.0e+99;
 
    for (int j = 0; j < N; ++j)
    {
 
        // Projection from all N points
        // on X-axis
        double px = Math.Cos(2 * pi * j / N +
                                proAngleVar);
 
        // Projection from all N points
        // on Y-axis
        double py = Math.Sin(2 * pi * j / N +
                                proAngleVar);
 
        negX = Math.Min(negX, px);
        posX = Math.Max(posX, px);
        negY = Math.Min(negY, py);
        posY = Math.Max(posY, py);
    }
 
    // Maximum side
    double opt2 = Math.Max(posX - negX,
                           posY - negY);
 
    // Return the portion of side
    // forming the square
    return (double)opt2 /
            Math.Sin(pi / N) / 2;
}
 
// Driver code
public static void Main()
{
    int N = 10;
    Console.Write(string.Format("{0:F5}", nGon(N)));
}
}
 
// This code is contributed by Nidhi_biet

Javascript

<script>
// Javascript program to find the minimum
// side of the square in which
// a regular polygon with even sides
// can completely embed
 
 
    // PI value in Java using
    // acos function
     let pi = Math.acos(-1.0);
 
    // Function to find the minimum
    // side of the square in which
    // a regular polygon with even sides
    // can completely embed
    function nGon( N) {
 
        // Projection angle variation
        // from axes
        let proAngleVar;
 
        // Projection angle variation
        // when the number of
        // sides are in multiple of 4
        if (N % 4 == 0) {
            proAngleVar = pi * (180.0 / N) / 180;
        } else {
            proAngleVar = pi * (180.0 / (2 * N)) / 180;
        }
 
        // Distance between the end points
        let negX = 1.0e+99, posX = -1.0e+99, negY = 1.0e+99, posY = -1.0e+99;
 
        for ( let j = 0; j < N; ++j) {
 
            // Projection from all N points
            // on X-axis
            let px = Math.cos(2 * pi * j / N + proAngleVar);
 
            // Projection from all N points
            // on Y-axis
            let py = Math.sin(2 * pi * j / N + proAngleVar);
 
            negX = Math.min(negX, px);
            posX = Math.max(posX, px);
            negY = Math.min(negY, py);
            posY = Math.max(posY, py);
        }
 
        // Maximum side
        let opt2 = Math.max(posX - negX, posY - negY);
 
        // Return the portion of side
        // forming the square
        return  opt2 / Math.sin(pi / N) / 2;
    }
 
    // Driver code
    let N = 10;
    document.write(nGon(N).toFixed(5));
 
// This code is contributed by Princi Singh
</script>
Producción: 

3.19623

 

Complejidad temporal: O(N) , donde N es el número de lados del polígono.
 

Publicación traducida automáticamente

Artículo escrito por mayur_patil y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA

Deja una respuesta

Tu dirección de correo electrónico no será publicada. Los campos obligatorios están marcados con *