Given three points of a regular polygon( n > 3), find the minimum area of a regular polygon (all sides same) possible with the points given .

**Examples:**

Input : 0.00 0.00 1.00 1.00 0.00 1.00 Output : 1.00 By taking point (1.00, 0.00) square is formed of side 1.0 so area = 1.00 .

One thing to note in question before we proceed is that the number of sides must be at least 4 (note n > 3 condition)..

Here, we have to find the minimum area possible for a regular polygon, so to calculate minimum possible area, we need calculate required value of n . As the side length is not given, so we first calculate **circumradius of the triangle** formed by the points. It is given by the formula

**R = abc / 4A**

where a, b, c are the sides of the triangle formed and A is the area of the traingle. Here, the area of triangle can be calculated by **Heron’s Formula** .

After calculating circumradius of the triangle, we calculate the area of the polygon by the formula

**A = nX ( sin(360/n) xr ^{2} /2 )**

Here r represents the circumradius of n-gon ( regular polygon of n sides ) .

But, first we have to calculate value of n . To calculate n we first have to calculate all the angles of triangle by the **cosine formula**

**cosA = ( b ^{2}+c^{2}-a^{2} ) / 2bc **

**cosB = ( a**

^{2}+c^{2}-b^{2}) / 2ac**cosC = ( a**

^{2}+b^{2}-c^{2}) / 2abThen, n is given by

** n = pi / GCD (A , B, C )**

where A, B and C are the angles of the triangle . After calculating n we substitute this value to the formula for calculating area of polygon .

Below is the implementation of the given approach :

## C++

`// CPP program to find minimum area of polygon of ` `// number of sides more than three with given three points. ` `#include <bits/stdc++.h> ` `using` `namespace` `std; ` ` ` `// assigning pi value to variable ` `const` `double` `pi = 3.14159265359; ` ` ` `// calculating gcd value of two double values . ` `double` `gcd(` `double` `x, ` `double` `y) ` `{ ` ` ` `return` `fabs` `(y) < 1e-4 ? x : gcd(y, ` `fmod` `(x, y)); ` `} ` ` ` `// Calculating minimum area of polygon through this function . ` `double` `min_area_of_polygon(` `double` `Ax, ` `double` `Ay, ` `double` `Bx, ` ` ` `double` `By, ` `double` `Cx, ` `double` `Cy) ` `{ ` ` ` `double` `a, b, c, Radius, Angle_A, Angle_B, Angle_C, ` ` ` `semiperimeter, n, area; ` ` ` ` ` `// calculating the length of the sides of the triangle ` ` ` `// formed from given points a, b, c represents the ` ` ` `// length of different sides of triangle . ` ` ` `a = ` `sqrt` `((Bx - Cx) * (Bx - Cx) + (By - Cy) * (By - Cy)); ` ` ` `b = ` `sqrt` `((Ax - Cx) * (Ax - Cx) + (Ay - Cy) * (Ay - Cy)); ` ` ` `c = ` `sqrt` `((Ax - Bx) * (Ax - Bx) + (Ay - By) * (Ay - By)); ` ` ` ` ` `// here we have calculated the semiperimeter of a triangle . ` ` ` `semiperimeter = (a + b + c) / 2; ` ` ` ` ` `// Now from the semiperimeter area of triangle is derived ` ` ` `// through the heron's formula . ` ` ` `double` `area_triangle = ` `sqrt` `(semiperimeter * (semiperimeter - a) ` ` ` `* (semiperimeter - b) ` ` ` `* (semiperimeter - c)); ` ` ` ` ` `// thus circumradius of the triangle is derived from the ` ` ` `// sides and area of the triangle calculated . ` ` ` `Radius = (a * b * c) / (4 * area_triangle); ` ` ` ` ` `// Now each angle of the triangle is derived from the sides ` ` ` `// of the triangle . ` ` ` `Angle_A = ` `acos` `((b * b + c * c - a * a) / (2 * b * c)); ` ` ` `Angle_B = ` `acos` `((a * a + c * c - b * b) / (2 * a * c)); ` ` ` `Angle_C = ` `acos` `((b * b + a * a - c * c) / (2 * b * a)); ` ` ` ` ` `// Now n is calculated such that area is minimum for ` ` ` `// the regular n-gon . ` ` ` `n = pi / gcd(gcd(Angle_A, Angle_B), Angle_C); ` ` ` ` ` `// calculating area of regular n-gon through the circumradius ` ` ` `// of the triangle . ` ` ` `area = (n * Radius * Radius * ` `sin` `((2 * pi) / n)) / 2; ` ` ` ` ` `return` `area; ` `} ` ` ` `int` `main() ` `{ ` ` ` `// three points are given as input . ` ` ` `double` `Ax, Ay, Bx, By, Cx, Cy; ` ` ` `Ax = 0.00; ` ` ` `Ay = 0.00; ` ` ` `Bx = 1.00; ` ` ` `By = 1.00; ` ` ` `Cx = 0.00; ` ` ` `Cy = 1.00; ` ` ` ` ` `printf` `(` `"%.2f"` `, min_area_of_polygon(Ax, Ay, Bx, By, Cx, Cy)); ` ` ` `return` `0; ` `} ` |

## Python3

`# Python3 program to find minimum area of ` `# polygon of number of sides more than three ` `# with given three points. ` ` ` `# from math lib import every function ` `from` `math ` `import` `*` ` ` `# assigning pi value to variable ` `pi ` `=` `3.14159265359` ` ` `# calculating gcd value of two double values . ` `def` `gcd(x, y) : ` ` ` ` ` `if` `abs` `(y) < ` `1e` `-` `4` `: ` ` ` `return` `x ` ` ` `else` `: ` ` ` `return` `gcd(y, fmod(x, y)) ` ` ` ` ` `# Calculating minimum area of polygon ` `# through this function . ` `def` `min_area_of_polygon(Ax, Ay, Bx, ` ` ` `By, Cx, Cy) : ` ` ` ` ` `# calculating the length of the sides of ` ` ` `# the triangle formed from given points ` ` ` `# a, b, c represents the length of different ` ` ` `# sides of triangle ` ` ` `a ` `=` `sqrt((Bx ` `-` `Cx) ` `*` `(Bx ` `-` `Cx) ` `+` ` ` `(By ` `-` `Cy) ` `*` `(By ` `-` `Cy)) ` ` ` `b ` `=` `sqrt((Ax ` `-` `Cx) ` `*` `(Ax ` `-` `Cx) ` `+` ` ` `(Ay ` `-` `Cy) ` `*` `(Ay ` `-` `Cy)) ` ` ` `c ` `=` `sqrt((Ax ` `-` `Bx) ` `*` `(Ax ` `-` `Bx) ` `+` ` ` `(Ay ` `-` `By) ` `*` `(Ay ` `-` `By)) ` ` ` ` ` `# here we have calculated the semiperimeter ` ` ` `# of a triangle . ` ` ` `semiperimeter ` `=` `(a ` `+` `b ` `+` `c) ` `/` `2` ` ` ` ` `# Now from the semiperimeter area of triangle ` ` ` `# is derived through the heron's formula ` ` ` `area_triangle ` `=` `sqrt(semiperimeter ` `*` ` ` `(semiperimeter ` `-` `a) ` `*` ` ` `(semiperimeter ` `-` `b) ` `*` ` ` `(semiperimeter ` `-` `c)) ` ` ` ` ` `# thus circumradius of the triangle is derived ` ` ` `# from the sides and area of the triangle calculated ` ` ` `Radius ` `=` `(a ` `*` `b ` `*` `c) ` `/` `(` `4` `*` `area_triangle) ` ` ` ` ` `# Now each angle of the triangle is derived ` ` ` `# from the sides of the triangle ` ` ` `Angle_A ` `=` `acos((b ` `*` `b ` `+` `c ` `*` `c ` `-` `a ` `*` `a) ` `/` `(` `2` `*` `b ` `*` `c)) ` ` ` `Angle_B ` `=` `acos((a ` `*` `a ` `+` `c ` `*` `c ` `-` `b ` `*` `b) ` `/` `(` `2` `*` `a ` `*` `c)) ` ` ` `Angle_C ` `=` `acos((b ` `*` `b ` `+` `a ` `*` `a ` `-` `c ` `*` `c) ` `/` `(` `2` `*` `b ` `*` `a)) ` ` ` ` ` `# Now n is calculated such that area is ` ` ` `# minimum for the regular n-gon ` ` ` `n ` `=` `pi ` `/` `gcd(gcd(Angle_A, Angle_B), Angle_C) ` ` ` ` ` `# calculating area of regular n-gon through ` ` ` `# the circumradius of the triangle ` ` ` `area ` `=` `(n ` `*` `Radius ` `*` `Radius ` `*` ` ` `sin((` `2` `*` `pi) ` `/` `n)) ` `/` `2` ` ` ` ` `return` `area ` ` ` `# Driver Code ` `if` `__name__ ` `=` `=` `"__main__"` `: ` ` ` ` ` `# three points are given as input . ` ` ` `Ax ` `=` `0.00` ` ` `Ay ` `=` `0.00` ` ` `Bx ` `=` `1.00` ` ` `By ` `=` `1.00` ` ` `Cx ` `=` `0.00` ` ` `Cy ` `=` `1.00` ` ` ` ` `print` `(` `round` `(min_area_of_polygon(Ax, Ay, Bx, ` ` ` `By, Cx, Cy), ` `1` `)) ` ` ` `# This code is contributed by Ryuga ` |

**Output:**

1.00

## leave a comment

## 0 Comments