|
ICPC2012に~shiokawaで参加したnotと言います。
結果は予選落ち最高位でした。無念。
参加記を書こうかと思ったんですがむちゃくちゃ暗い内容になったのでやめました。
そのかわりに、幾何ライブラリを作って思ったことをつらつらと書いていきます。
ライブラリの整理は2ヶ月前くらいからゆるゆるとやっていました。
この間、ライブラリの実装方針は二転三転しました。
気をつけたのは以下のような点です。
はじめは自分でクラスを定義するライブラリを書いていましたが、途中でcomplexに切り替えました。
理由は「ライブラリを写す時間を短縮したい！！」ってだけです。
ICPCはなんせキーボードに触れる時間が限定されるのでライブラリは短いほうがいいです。
complexは始めから色々と定義されているのでライブラリコピペ時間が減らせます。
そのかわり、double型を代入してもコンパイルできてしまうという致命的欠陥があるのでコーディング時に気をつける必要があります。
ライブラリを写す必要のないコンテストでは自作クラスのほうが良いかもしれません。
関数名は自分が分かる範囲で出来る限り短くしました。
理由は上と同じでライブラリ圧縮のためです。
他人に見せるコードでもないので自分たちがわかる関数名ならなんでも良いと思います。
どの部分を関数にするかはかなり迷いました。
例えば「線分に垂直な単位ベクトル」を関数として定義する必要があるのか？といったことです。
基本的な方針は「本番のコーディング量を減らそう！」だったので他の関数への依存性をできるだけ減らすようにしました。
なので、上のような関数は定義しないようにしました。
ライブラリで定義する関数の結果はすべて返り値で返すようにしました。
これは単なる好みの問題だと思うのでどうでもいいですが、自分が書きやすいように統一したほうがいいです。
Verifyは問題を解く以外ではほとんどやっていません。
ただし、特定の問題で致命的にならないバグがあったりすることもあるので計算中の結果を確認したりすることはありました。
（Verifyについてはもっと効率の良い手法を考えていますがいつ完成するかわかりません…。）
ICPCはTLEが存在しないので速度はほとんど気にしませんでした。
inlineとかも「タイプ量の無駄！」と判断して全くしていません。
ただし、偏角ソートで偏角が同じ時にabsで比較するのではなくnormを使うなどコード量に関係ない高速化はしました。
ライブラリで主に使ったのは以下の関数でした。
必要な関数は問題をどう実装するのが好きかにもよって変わってくると思いますがこれくらいはあったほうがいいと思います。
三角形の外心などどうせいらないけどないと不安なものは数式を印刷して持ち込みました。
同一直線上にある場合に交差しているとみなすかどうかは気をつけるべきです。
自分のライブラリでは同一直線上も交差しているとみなしているので「直線が交差する≠交点が定義できる」という仕様でした。
円が他の円に含まれたり接したりする交差したりする判定をどの程度細かくするかは好みによると思います。
自分のライブラリでは「同じ・含む・含まれる・共有点なし・含んで内側で接する・含まれて内側で接する・外側で接する・共有点２個」で分類しました。
やや細かすぎるかもしれません。もう少し大雑把でも良いかも。
epsは基本的に10^-8でやっていました。普通はこれで大丈夫のようです。
sqrtなどに負の数を渡したりするとnanが出るので気をつけましょう。
sqrt(max(..., 0.0))が基本形です。
かなり細かいですがcomplexにはpolarという関数があって便利です。
…が、この関数は第二引数（偏角）を省略できるというクソ仕様があるのでpolar(1., -theta)と書こうとしてpolar(1. -theta)と書いてWAを食らったことがあります。気をつけましょう。
交差判定をするときに線分の端点を含めるかどうかはしっかり意識しましょう。
自分のライブラリでは端点を含めるかどうかで関数を２種類ずつ用意しています。
細かいところまで突っ込んだのでだいぶ長くなってしまいました。
一番言いたかったのはICPCは時間がないので自分がパパっと使えるライブラリを作りましょうということです。
いいライブラリを作るにはそれなりに問題数を解く必要があります。頑張りましょう。
