C++で四辺形の最大面積を求める方法

問題文

四辺形の4つの辺 a、b、c、d が与えられたとき、それらの辺から構成できる四辺形の最大面積を求めることを考えます。

アルゴリズム

この問題は、古代インドの数学者ブラーマグプタ(Brahmagupta)による次の公式を利用することで解くことができます。

√(s−a)(s−b)(s−c)(s−d)

ここで、s は半周長(semi-perimeter)と呼ばれる値であり、次のように計算します。

S = (a + b + c + d) / 2

なお、ブラーマグプタの公式は本来、円に内接する四辺形に対して成立するものですが、与えられた4つの辺の長さを持つすべての四辺形の中では、円に内接する四辺形が最大の面積を持つことが知られています。そのため、この公式を使うことで「与えられた辺から作れる最大の面積」を正しく求めることができます。

コード例

それでは、実際のC++コードを見てみましょう。

#include <bits/stdc++.h>
using namespace std;
double getMaxArea(double a, double b, double c, double d) {
   double s = (a + b + c + d) / 2;
   double area = (s - a) * (s - b) * (s - c) * (s - d);
   return sqrt(area);
}
int main() {
   double a = 1, b = 2.5, c = 1.8, d = 2;
   cout << "Maximum area = " << getMaxArea(a, b, c, d) << endl;
   return 0;
}

出力結果

Maximum area = 3.05

この例では、辺の長さがそれぞれ 1、2.5、1.8、2 の四辺形について、半周長 s = 3.65 が求められ、各項 (s−a)、(s−b)、(s−c)、(s−d) を掛け合わせて平方根を取ることで、最大面積が約 3.05 であることが分かります。