Codeforces 1C

典型的な誤差について考える幾何の問題。

問題

正N角形の頂点のうちの三つが指定されるので、可能な正N角形のうち、一番小さいものの面積を答えよ、という問題。

解答例

外心を計算して、各頂点との間でなす角の角度を求めてやる。それが正N角形のNを指定したときに、可能なものである最小のNを求めてやれば良い。後は外接円の半径が分かれば、二等辺三角形がN個あるだけなので、面積は求まる。

この問題の肝は、二つの角度から、他方がもう一方の整数倍であるかどうかを判定することで、このときに使う誤差判定の式をまじめに吟味する必要がある。問題文中で正100角形程度までに答えが存在すると言っている時点で、余り厳密な計算はできないと判断するべきらしいが...。

なお、三点からなる三角形の三つの角の角度を求めてやれば、外心と各頂点を結んでできる角の角度はそれらの倍になる。外接円の半径を求める公式もあるので、外心は求めなくても良い。