# Minimum area of a Polygon with three points given

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 the minimum possible area, we need to calculate the required value of n. As the side length is not given, so we first calculate the **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 triangle. Here, the area of the 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;` `}` |

## Java

`// Java program to find minimum` `// area of polygon of number of` `// sides more than three with` `// given three points.` `class` `GFG{` `// Assigning pi value to variable` `static` `double` `pi = ` `3.14159265359` `;` ` ` `public` `static` `double` `fmod(` `double` `a,` ` ` `double` `b)` `{` ` ` `int` `result = (` `int` `) Math.floor(a / b);` ` ` `return` `a - result * b;` `}` ` ` `// calculating gcd value of` `// two double values .` `public` `static` `double` `gcd(` `double` `x,` ` ` `double` `y)` `{` ` ` `return` `Math.abs(y) < 1e-` `4` `? x :` ` ` `gcd(y, fmod(x, y));` `}` ` ` `// Calculating minimum area of polygon through this function .` `public` `static` `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 = Math.sqrt((Bx - Cx) * (Bx - Cx) +` ` ` `(By - Cy) * (By - Cy));` ` ` `b = Math.sqrt((Ax - Cx) * (Ax - Cx) +` ` ` `(Ay - Cy) * (Ay - Cy));` ` ` `c = Math.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 = Math.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 = Math.acos((b * b + c * c - a * a) /` ` ` `(` `2` `* b * c));` ` ` `Angle_B = Math.acos((a * a + c * c - b * b) /` ` ` `(` `2` `* a * c));` ` ` `Angle_C = Math.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 *` ` ` `Math.sin((` `2` `* pi) / n)) / ` `2` `;` ` ` `return` `area;` `}` ` ` `// Driver code` `public` `static` `void` `main(String[] args)` `{` ` ` `// 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` `;` ` ` `System.out.println(String.format(` `"%.2f"` `,` ` ` `min_area_of_polygon(Ax, Ay,` ` ` `Bx, By,` ` ` `Cx, Cy)));` `}` `}` `// This code is contributed by divyeshrabadiya07` |

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

## C#

`// C# program to find minimum` `// area of polygon of number of` `// sides more than three with` `// given three points. ` `using` `System;` `using` `System.Collections.Generic;` `class` `GFG` `{` ` ` ` ` `// Assigning pi value to variable` ` ` `static` `double` `pi = 3.14159265359;` ` ` ` ` `static` `double` `fmod(` `double` `a, ` `double` `b)` ` ` `{` ` ` `int` `result = (` `int` `) Math.Floor(a / b);` ` ` `return` `a - result * b;` ` ` `}` ` ` ` ` `// calculating gcd value of` ` ` `// two double values .` ` ` `static` `double` `gcd(` `double` `x, ` `double` `y)` ` ` `{` ` ` `return` `Math.Abs(y) < 1e-4 ? x : gcd(y, fmod(x, y));` ` ` `}` ` ` ` ` `// Calculating minimum area of polygon through this function .` ` ` `static` `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 = Math.Sqrt((Bx - Cx) * (Bx - Cx) +` ` ` `(By - Cy) * (By - Cy));` ` ` `b = Math.Sqrt((Ax - Cx) * (Ax - Cx) +` ` ` `(Ay - Cy) * (Ay - Cy));` ` ` `c = Math.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 = Math.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 = Math.Acos((b * b + c * c - a * a) /` ` ` `(2 * b * c));` ` ` `Angle_B = Math.Acos((a * a + c * c - b * b) /` ` ` `(2 * a * c));` ` ` `Angle_C = Math.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 *` ` ` `Math.Sin((2 * pi) / n)) / 2;` ` ` ` ` `return` `area;` ` ` `} ` ` ` ` ` `// Driver code` ` ` `static` `void` `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;` ` ` `Console.WriteLine(String.Format(` `"{0:0.00}"` `, min_area_of_polygon(Ax, Ay,` ` ` `Bx, By,` ` ` `Cx, Cy)));` ` ` `}` `}` `// This code is contributed by divyeshrabadiya07` |

## Javascript

`<script>` `// Javascript program to find minimum` `// area of polygon of number of` `// sides more than three with` `// given three points.` `// Assigning pi value to variable` `let pi = 3.14159265359;` `function` `fmod(a, b) {` ` ` `let result = Math.floor(a / b);` ` ` `return` `a - result * b;` `}` `// calculating gcd value of` `// two double values .` `function` `gcd(x, y) {` ` ` `return` `Math.abs(y) < 1e-4 ? x :` ` ` `gcd(y, fmod(x, y));` `}` `// Calculating minimum area of polygon through this function .` `function` `min_area_of_polygon(Ax, Ay, Bx, By, Cx, Cy) {` ` ` `let 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 = Math.sqrt((Bx - Cx) * (Bx - Cx) +` ` ` `(By - Cy) * (By - Cy));` ` ` `b = Math.sqrt((Ax - Cx) * (Ax - Cx) +` ` ` `(Ay - Cy) * (Ay - Cy));` ` ` `c = Math.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 .` ` ` `let area_triangle = Math.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 = Math.acos((b * b + c * c - a * a) /` ` ` `(2 * b * c));` ` ` `Angle_B = Math.acos((a * a + c * c - b * b) /` ` ` `(2 * a * c));` ` ` `Angle_C = Math.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 *` ` ` `Math.sin((2 * pi) / n)) / 2;` ` ` `return` `area;` `}` `function` `to_fixed(float, pre) {` ` ` `let x = ` `new` `String(float).split(` `"."` `)` ` ` `return` `x[0] + ` `"."` `+ x[1].slice(0, pre)` `}` `// Driver code` `// Three points are given as input .` `let Ax, Ay, Bx, By, Cx, Cy;` `Ax = 0.00;` `Ay = 0.00;` `Bx = 1.00;` `By = 1.00;` `Cx = 0.00;` `Cy = 1.00;` `document.write(to_fixed(min_area_of_polygon(Ax, Ay, Bx, By, Cx, Cy), 2));` ` ` `// This code is contributed by Saurabh Jaiswal` `</script>` |

**Output:**

1.00

**Time complexity :** O(log(min(A,B,C)))

**Auxiliary Space : **O(1), since no extra space has been taken.