幾何のテストケースの作り方
これはCompetitive Programming Advent Calendar 2014に投稿された記事です。
ICPCではいる君に幾何は任せていたので担当ではないのですが、JAGに入ってからは何故か高頻度で幾何の担当になってしまっています。幾何のプロがJAGに入ってもう当たらんだろうと思ったら、この前のICPC模擬地区予選も幾何が2問あって結局データセットを作ってました。
というわけで今まで作ってきたテストケースの手法を書いていきます。
2次元幾何の場合
最低限、コーナーケースや誤差死を防ぐための制約などの洗い出しは事前にやっておきましょう。
generatorを作るのが難しい場合は問題自体を少し変えるのも有りです。例えば、流れ星に願いをでは、当初は最後の星が消える時間のみを出力する予定だったのですが、1つのテストケースで落とせる確率が無駄に減るので、星が消える時間を全て出力するようにしました。
ランダムに作る
点の位置くらいしかない場合はランダム生成でもある程度機能します。この時ランダムの分布をいじって偏りのあるケースなども作っておくと良いです。例えば、平行な線分がコーナーケースの場合はそういったものが多く出るようにします。もしくは、誤答を先に作っておいて誤答になるケースが出るまで生成するというのもありです。
注意点としては、問題によっては生成した入力が、幾何でよくある「EPS以下の距離には〜が無い」といった制約に引っかかる場合があります。そういった制約に引っかかる場合はgeneratorの中でvalidatorを動かして、そういった入力があったら再生成してしまいましょう。あまり適当にやっているとgeneratorが無限ループにおちいる場合もあるので、一旦小さいサイズで生成し、validatorが通ったらサイズを徐々に大きくするなどもありです。
人力で作る
ランダムだけではまともなケースを作るのが厳しい、例えば自己交差の無い多角形とかグラフ要素が混ざってくる場合などです。個別のテストケースを1つずつプログラムを書いて作るのは大変すぎるので、手で作ってしまうのが楽です。
私はdiaというダイアグラム作成ツールでテストケースを作成しています。diaで線分、多角形、折れ線などベクター画像を書き、svgで出力し、C++でパースして問題の入力に変換してます。多角形の頂点の追加などが面倒ですが、100頂点くらいの物ならこれで作れると思います。
色も付けれますし、コピペもできるのでこんくらいのテストケースならすぐに作れます。ただし、入力サイズが大きかったり、数値をちゃんと計算しないと作れないコーナーケース等を作るのは難しいので、プログラムを書いて生成するのと併用する必要があります。
3次元幾何の場合
頑張ってください。
人力でやるのはかなり無理があるので、プログラムを書くしか無いと思います。
テクニックとしては、z=0の入力を作る際は2次元と同じ方法が使えます。縮退した入力はどっちみち必要になるので、2次元で落とせる解答は2次元で落としましょう。3次元の入力が弱くてもなんとかなるかもしれません。
また、ランダムな正規直交基底(平面)を作りたい場合はランダムなベクトルを作って、と外積を2回かけるとできます。
ビジュアライズする
ply形式で保存すると楽です。ply形式は下のような感じのtxtファイルで、ちゃんとヘッダーを書けばポリゴンも扱えます。
ply format ascii 1.0 element vertex 2000 property float x property float y property float z property uchar diffuse_red property uchar diffuse_green property uchar diffuse_blue end_header 1.122748 2.322027 2.471454 255 0 0 1.125541 2.323361 2.465986 255 0 0 1.128307 2.324675 2.460499 255 0 0 1.131045 2.325967 2.454994 255 0 0 1.133755 2.327239 2.449470 255 0 0 1.136438 2.328489 2.443927 255 0 0 1.139093 2.329717 2.438367 255 0 0 ...
ply形式はMeshLab等で見ることが可能です。以下はRingsのデータです。
まとめ
というわけでこんな感じで幾何のテストケースを作ってきました。幾何はやる事が多くて時間がかかる上にめんどくさいので早めに取りかからないと死にます。
あと、やる気のある人はJAGに入って作っていただけるとありがたいです。
担当した幾何問題一覧
最終防衛問題は解けないので担当してません(あと最近ないし)
テストケースを作った問題
- ふか杯5th/IRU vs SAKI(原案担当)
- ICPC模擬国内予選2012/ドッグフード
- JAG夏合宿2012/Area Folding
- JAG春コンテスト2012/Rings
- ICPC模擬国内予選2014/流れ星に願いを
- ICPC模擬地区予選2014/Color the Map Extreme
解答のみ