ch19-smallest-enclosing-circle
テスト
入力フォルダを用意する
入力する点群の情報を含んだテキストファイルをこのフォルダに与える。
プログラムはここからテキストファイルを読み取って期待値との比較を行う
結果出力はコンソールに行う
結果の判定: AC.iconかWA.iconを返す
用意すべきテストケース
TODO それぞれに対して具体的に点群を生成するコードを記述する
rand = 制約を満たしながら点群をランダムに配置したケースを指す
1. 数が少ないケース
N = 0 : 1ケース
N = 1 : 3ケース
N = 2 : 3ケース
N = 3 : 5ケース
鋭角三角形 x 1
鈍角三角形 x 1
rand x 3
N = 4: 7ケース
鋭角三角形2つからなる四角形 x 1
鈍角三角形2つからなる四角形 x 1
鈍角三角形と鈍角三角形からなる四角形 x 1
同一円周上にある4点からなる四角形 x 1
rand x 3
2. 数が多いケース: 40ケース
$ N = 1 \times 10^4 x 10ケース
$ N = 2 \times 10^5 x 15ケース
$ N = 4 \times 10^7 x 15ケース
点の分布はどうする?
正規分布以外でもいいかもしれないappbird.icon
3. 全ての点が一直線上にあるケース : 3ケース
N = 100におけるケース
一点を除き、全ての点が一直線に並んでいるケース
各々の4点が同一直線上に存在するケース
4. 4点以上が同一円周上にあるケース: 4ケース
$ N = 100で、全ての点が半径300の円に存在する
$ N = 100点のうち、$ 1点を除きすべての点が半径300の円に存在する
$ N = 100点のうち、$ 2点を除きすべての点が半径300の円に存在する
$ N = 100 = 4 \cdot 25で、各々の4点がランダムな円上に存在するケース
5. 座標値が巨大なケース: 3ケース
原点からの距離$ Rが$ R \simeq 1 \times 10^{18}であるような領域中の点を中心とする、半径500の円上に分布する点群のケース
原点中心・半径$ R \simeq 1 \times 10^{18}の円上に分布する点のケース
もっと座標値が大きいケースも考慮するべき?($ 10^{300}とか)appbird.icon
6. シャッフルしないと計算量が爆発するケース: 1ケース
以下のような方法で構成される点群について求める
$ N = 300
code:cpp
for (int32 i = 0; i < N; ++i)
{
pointsi = OffsetCircular{ Scene::CenterF(), (200.0 * i / N), (120_deg * i) }; }
7. すべて同一点であるようなケース: 2ケース
$ N \geq 2 rand x 2
8. 一部が同一点であるようなケース: 4ケース
$ N \geq 2, $ N /2点が同一点上に存在 x 2
$ N \geq 3, $ N /3点がある一点上に存在, それとは異なる$ N / 3点が別の一点上に存在 x 2