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