Dado un polígono convexo regular de N lados y un ángulo A en grados, la tarea es encontrar 3 vértices cualesquiera i , j y k , de modo que el ángulo subtendido en el vértice j por el vértice i y k sea el más cercano a A.
Nota: Cada vértice está numerado del 1 al N en sentido antihorario a partir de cualquier vértice.
Ejemplos:
Entrada: N = 3, A = 15
Salida: 2 1 3
Explicación:
El polígono dado es un triángulo, por lo tanto, el ángulo mínimo que se puede subtender en cualquier vértice es igual a 30, que es el más cercano a A e incluye todos los vértices del polígono.Entrada: N = 4, A = 90
Salida: 2 1 4
Enfoque: El problema dado se puede resolver con base en las siguientes observaciones:
- Los vértices de un polígono regular se encuentran en un círculo.
- El ángulo central de un polígono regular de n lados es 360/N .
- El ángulo subtendido en el centro del círculo por vértices separados por X aristas es igual a (360*X)/N .
- Por el teorema, el ángulo subtendido en la circunferencia circunscrita por un arco es la mitad del ángulo subtendido en el centro por el mismo arco. Por tanto, el ángulo subtendido en un vértice por un arco formado por X aristas sería igual a (180*X)/N .
- Como el polígono es regular, por lo tanto, el mismo ángulo se puede subtender tomando 2 vértices cualesquiera de diferencia de borde igual a X .
Siga los pasos a continuación para resolver el problema:
- Inicialice dos variables, digamos ans como 0 y minElement como INT_MAX para almacenar el recuento de aristas que subtiende el ángulo más cercano a A y para almacenar el ángulo más cercano respectivamente.
- Iterar sobre el rango [1, N – 2] usando la variable i y realizar los siguientes pasos:
- Encuentre el ángulo subtendido en un círculo circunscrito por un arco formado por aristas i usando la fórmula anterior y guárdelo en un ángulo variable.
- Compruebe si el valor absoluto de (A – angle) es menor que el valor absoluto de (minElement – A) , luego actualice el valor de i a ans y el valor de angle a minElement .
- Después de completar los pasos anteriores, imprime los vértices {2, 1, 2 + ans} como los vértices resultantes.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ program for the above approach
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define MAXN 1000000
// Function to find three vertices that
// subtends an angle closest to A
void closestsAngle(int N, int A)
{
// Stores the closest angle to A
double mi = INT_MAX;
// Stores the count of edge which
// subtend an angle of A
int ans = 0;
// Iterate in the range [1, N-2]
for (int i = 1; i < N - 1; i++) {
// Stores the angle subtended
double angle = 180.0 * i / N;
// If absolute(angle-A) is less
// than absolute(mi-A)
if (fabs(angle - A) < fabs(mi - A)) {
// Update angle to mi, and
// also update i to ans
mi = angle;
ans = i;
}
}
// Print the vertices
cout << 2 << ' ' << 1 << ' '
<< 2 + ans;
}
// Driver Code
int main()
{
int N = 3, A = 15;
closestsAngle(N, A);
return 0;
}
Java
// Java program for the above approach
import java.io.*;
class GFG {
// Function to find three vertices that
// subtends an angle closest to A
static void closestsAngle(int N, int A)
{
// Stores the closest angle to A
double mi = Integer.MAX_VALUE;
// Stores the count of edge which
// subtend an angle of A
int ans = 0;
// Iterate in the range [1, N-2]
for (int i = 1; i < N - 1; i++) {
// Stores the angle subtended
double angle = 180.0 * i / N;
// If absolute(angle-A) is less
// than absolute(mi-A)
if (Math.abs(angle - A) < Math.abs(mi - A)) {
// Update angle to mi, and
// also update i to ans
mi = angle;
ans = i;
}
}
// Print the vertices
System.out.print(2 + " " + 1 + " " + (2 + ans));
}
// Driver Code
public static void main(String[] args)
{
int N = 3, A = 15;
closestsAngle(N, A);
}
}
// This code is contributed by subhammahato348.
Python3
# Python program for the above approach # Function to find three vertices that # subtends an angle closest to A import math import sys def closestsAngle(N, A): # Stores the closest angle to A mi = sys.maxsize # Stores the count of edge which # subtend an angle of A ans = 0 # Iterate in the range [1, N-2] for i in range(N ): # Stores the angle subtended angle = 180.0 * i / N # If absolute(angle-A) is less # than absolute(mi-A) if (math.fabs(angle - A) < math.fabs(mi - A)): # Update angle to mi, and # also update i to ans mi = angle i+=1 ans = i # Pr the vertices print(2 , 1 , 2 + ans) # Driver Code if __name__ == '__main__': N = 3 A = 15 closestsAngle(N, A) # This code is contributed by Shivani
C#
// C# program for the above approach
using System;
class GFG{
// Function to find three vertices that
// subtends an angle closest to A
static void closestsAngle(int N, int A)
{
// Stores the closest angle to A
double mi = Int32.MaxValue;
// Stores the count of edge which
// subtend an angle of A
int ans = 0;
// Iterate in the range [1, N-2]
for(int i = 1; i < N - 1; i++)
{
// Stores the angle subtended
double angle = 180.0 * i / N;
// If absolute(angle-A) is less
// than absolute(mi-A)
if (Math.Abs(angle - A) <
Math.Abs(mi - A))
{
// Update angle to mi, and
// also update i to ans
mi = angle;
ans = i;
}
}
// Print the vertices
Console.Write(2 + " " + 1 +
" " + (2 + ans));
}
// Driver Code
public static void Main()
{
int N = 3, A = 15;
closestsAngle(N, A);
}
}
// This code is contributed by subhammahato348
Javascript
<script>
// JavaScript program for the above approach
// Function to find three vertices that
// subtends an angle closest to A
function closestsAngle(N, A) {
// Stores the closest angle to A
let mi = Number.MAX_VALUE;
// Stores the count of edge which
// subtend an angle of A
let ans = 0;
// Iterate in the range [1, N-2]
for (let i = 1; i < N - 1; i++) {
// Stores the angle subtended
let angle = 180.0 * i / N;
// If absolute(angle-A) is less
// than absolute(mi-A)
if (Math.abs(angle - A) < Math.abs(mi - A)) {
// Update angle to mi, and
// also update i to ans
mi = angle;
ans = i;
}
}
// Print the vertices
document.write(2 + ' ' + 1 + ' '
+ parseInt(2 + ans));
}
// Driver Code
let N = 3, A = 15;
closestsAngle(N, A);
// This code is contributed by Potta Lokesh
</script>
Producción:
2 1 3
Complejidad temporal: O(N)
Espacio auxiliar: O(1)
Publicación traducida automáticamente
Artículo escrito por ujjwalgoel1103 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA