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: 1
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>
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