C++でk個の等間隔点を持つ円における、指定した2点間の鈍角の数を求める方法

円周上にK個の等間隔（等距離）の点が配置された円が与えられます。さらに、2つの点AとBも与えられます。この記事の目的は、これらの点を使って構成できる三角形のうち、内部に90度より大きい鈍角ACBを持つものの数を数えることです。点AとBは常に A < B を満たすものとします。

下図の例では K=8、A=2、B=5 であり、∠ACB および ∠AC′B が鈍角になるような点は C と C′ の2つ存在します。

具体例で理解しよう

入力 − k=10、A=2、B=4

出力 − 2つの指定点間にk個の等間隔点を持つ円における鈍角の数 − 1

説明 − 条件を満たす点は C=3 のみです。

入力 − k=12、A=2、B=10

出力 − 2つの指定点間にk個の等間隔点を持つ円における鈍角の数 − 3

本プログラムで採用しているアプローチ

ここで重要なのは、AとBをつなぐ短い方の弧上にのみ、条件を満たす点が存在するという点です。

まず両方の弧の長さを計算し、もし2つの弧が同じ長さであれば、条件を満たす三角形は存在しないため0を返します。そうでなければ、カウントを短い方の弧の長さ（点の数としての距離）に設定します。

• 整数 k、point_a、point_b を入力として受け取ります。

• 関数 Obtuse_angle_circle(int point_a, int point_b, int k) がすべての変数を受け取り、2つの指定点間にk個の等間隔点を持つ円における鈍角の数を返します。

• 初期カウントを0に設定します。

• 最初の弧を arc_1 = (point_b - point_a) - 1 として計算します。（b > a の場合）

• 2番目の弧を arc_2 = (k - point_b) + (point_a - 1) として計算します。

• 両方の弧が等しい場合は、そのような点は存在しないため0を返します。

• 弧が等しくない場合は、すべての点が短い方の弧上に存在するため、カウントを2つの弧の最小値に更新します。

• カウントを結果として返します。

サンプルコード

#include <bits/stdc++.h>
using namespace std;
int Obtuse_angle_circle(int point_a, int point_b, int k){
    int count = 0;
    int arc_1 = (point_b - point_a) - 1;
    int arc_2 = (k - point_b) + (point_a - 1);
    if (arc_1 == arc_2){
        return 0;
    }
    count = min(arc_1, arc_2);
    return count;
}
int main(){
    int k = 10;
    int point_a= 1;
    int point_b = 4;
    cout<<"2つの指定点間にk個の等間隔点を持つ円における鈍角の数: "<<Obtuse_angle_circle(point_a, point_b, k);
    return 0;
}

出力

上記のコードを実行すると、次の出力が得られます −

2つの指定点間にk個の等間隔点を持つ円における鈍角の数: 2