Find three vertices in an N-sided regular polygon such that the angle subtended at a vertex by two other vertices is closest to A
Given an N-sided regular convex polygon and an angle A in degrees, the task is to find any 3 vertices i, j, and k, such that the angle subtended at vertex j by vertex i and k is closest to A.
Note: Each vertex is numbered from 1 to N in an anticlockwise direction starting from any vertex.
Examples:
Input: N = 3, A = 15
Output: 2 1 3
Explanation:
The given polygon is a triangle, therefore the minimum angle that can be subtended on any vertex is equal to 30 which is closest to A and includes all the vertices of the polygon.Input: N = 4, A = 90
Output: 2 1 4
Approach: The given problem can be solved based on the following observations:
- The vertices of a regular polygon lie on a circle.
- The central angle of n sided regular polygon is 360/N.
- The angle subtended on the center of the circle by vertices separated by X edges is equals to (360*X)/N.
- By the theorem, the angle subtended on the circum-circle by an arc is half of the angle subtended at the center by the same arc. Therefore, the angle subtended on a vertex by an arc formed by X edges would be equal to (180*X)/N.
- As the polygon is regular therefore the same angle can be subtended by taking any 2 vertices of edge difference equal to X.
Follow the steps below to solve the problem:
- Initialize two variables, say ans as 0 and minElement as INT_MAX to store the count of edges which subtends the angle closest to A and to store the closest angle respectively.
- Iterate over the range [1, N – 2] using the variable i and perform the following steps:
- Find the angle subtended on circum-circle by an arc formed by i edges using the above formula and store it in a variable, angle.
- Check if the absolute value of (A – angle) is less than the absolute value of (minElement – A), then update the value of i to ans and the value of angle to minElement.
- After completing the above steps, print the vertices {2, 1, 2 + ans} as the resultant vertices.
Below is the implementation of the above approach:
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> |
2 1 3
Time Complexity: O(N)
Auxiliary Space: O(1)