Hatena::Grouptopcoder

not's memo

2012-07-12

ぼくのかんがえたさいきょうのきからいぶらり(1)

22:20 | はてなブックマーク - ぼくのかんがえたさいきょうのきからいぶらり(1) - not's memo

ICPC2012に~shiokawaで参加したnotと言います。

結果は予選落ち最高位でした。無念。

参加記を書こうかと思ったんですがむちゃくちゃ暗い内容になったのでやめました。

そのかわりに、幾何ライブラリを作って思ったことをつらつらと書いていきます。

幾何ライブラリを書く前に

ライブラリの整理は2ヶ月前くらいからゆるゆるとやっていました。

この間、ライブラリの実装方針は二転三転しました。

気をつけたのは以下のような点です。

typedef complex<double> vs 自作クラス

はじめは自分でクラスを定義するライブラリを書いていましたが、途中でcomplexに切り替えました。

理由は「ライブラリを写す時間を短縮したい!!」ってだけです。

ICPCはなんせキーボードに触れる時間が限定されるのでライブラリは短いほうがいいです。

complexは始めから色々と定義されているのでライブラリコピペ時間が減らせます。

そのかわり、double型を代入してもコンパイルできてしまうという致命的欠陥があるのでコーディング時に気をつける必要があります。

ライブラリを写す必要のないコンテストでは自作クラスのほうが良いかもしれません。

関数名

関数名は自分が分かる範囲で出来る限り短くしました。

理由は上と同じでライブラリ圧縮のためです。

他人に見せるコードでもないので自分たちがわかる関数名ならなんでも良いと思います。

関数の切り分け・独立性

どの部分を関数にするかはかなり迷いました。

例えば「線分に垂直な単位ベクトル」を関数として定義する必要があるのか?といったことです。

基本的な方針は「本番のコーディング量を減らそう!」だったので他の関数への依存性をできるだけ減らすようにしました。

なので、上のような関数は定義しないようにしました。

参照渡し vs 返り値

ライブラリで定義する関数の結果はすべて返り値で返すようにしました。

これは単なる好みの問題だと思うのでどうでもいいですが、自分が書きやすいように統一したほうがいいです。

Verify

Verifyは問題を解く以外ではほとんどやっていません。

ただし、特定の問題で致命的にならないバグがあったりすることもあるので計算中の結果を確認したりすることはありました。

(Verifyについてはもっと効率の良い手法を考えていますがいつ完成するかわかりません…。)

速度

ICPCはTLEが存在しないので速度はほとんど気にしませんでした。

inlineとかも「タイプ量の無駄!」と判断して全くしていません。

ただし、偏角ソートで偏角が同じ時にabsで比較するのではなくnormを使うなどコード量に関係ない高速化はしました。

必要な関数

ライブラリで主に使ったのは以下の関数でした。

必要な関数は問題をどう実装するのが好きかにもよって変わってくると思いますがこれくらいはあったほうがいいと思います。

  • 点と線分の関係(CCW)
  • 線分,直線,円の交差判定
  • 直線と直線,直線と円,円と円の交点
  • 点,線分,直線の距離
  • 射影・反射
  • ヘロンの公式
  • 多角形の面積
  • 多角形,角の内外判定
  • ソートの比較関数(x座標優先・y座標優先・偏角)
  • 凸包・凸多角形カット
  • 線分アレンジメント

三角形の外心などどうせいらないけどないと不安なものは数式を印刷して持ち込みました。

その他気をつけるべき細かい点

線分,直線の交差

同一直線上にある場合に交差しているとみなすかどうかは気をつけるべきです。

自分のライブラリでは同一直線上も交差しているとみなしているので「直線が交差する≠交点が定義できる」という仕様でした。

円と円の関係

円が他の円に含まれたり接したりする交差したりする判定をどの程度細かくするかは好みによると思います。

自分のライブラリでは「同じ・含む・含まれる・共有点なし・含んで内側で接する・含まれて内側で接する・外側で接する・共有点2個」で分類しました。

やや細かすぎるかもしれません。もう少し大雑把でも良いかも。

eps

epsは基本的に10^-8でやっていました。普通はこれで大丈夫のようです。

nan

sqrtなどに負の数を渡したりするとnanが出るので気をつけましょう。

sqrt(max(..., 0.0))が基本形です。

polar

かなり細かいですがcomplexにはpolarという関数があって便利です。

…が、この関数は第二引数(偏角)を省略できるというクソ仕様があるのでpolar(1., -theta)と書こうとしてpolar(1. -theta)と書いてWAを食らったことがあります。気をつけましょう。

線分の端点

交差判定をするときに線分の端点を含めるかどうかはしっかり意識しましょう。

自分のライブラリでは端点を含めるかどうかで関数を2種類ずつ用意しています。

まとめ

細かいところまで突っ込んだのでだいぶ長くなってしまいました。

一番言いたかったのはICPCは時間がないので自分がパパっと使えるライブラリを作りましょうということです。

いいライブラリを作るにはそれなりに問題数を解く必要があります。頑張りましょう。

ゲスト



トラックバック - http://topcoder.g.hatena.ne.jp/not522/20120712