幾何

ICPCでは幾何の問題が出題されることがありますが、幾何問題は簡単そうに見えて意外に難しいです。

具体的には、「2つの線分が交差しているか」「多角形の面積はいくらか」といった単純な問題でさえ、何の考えもなしにプログラムを組もうとすると泥沼にはまります。

例えば、先に挙げた「2つの線分が交差しているか」という問題に対し、線分をy=ax+bという直線の式を使って表して解こうとしたとしましょう。 この場合、ほとんどの場合は2つの線分の式を連立させれば解けますが、y=ax+bという形式で表せない直線(y軸に平行な直線)や2線分が同一直線上にある場合など考えなければいけない例外ケースが多く、複雑なコードになってしまいます。 多角形の面積の計算も、複数の三角形に分割してヘロンの公式を適用する…とのように解こうとしたら、凹みのある多角形の扱いが難しく、実装するのは想像以上に大変です。

できる限り幾何で悩まないためには、プログラム上で効率よく幾何問題を解くための基礎知識を学んでおくべきです。

プログラムで平面幾何問題を解く場合は、頂点は複素数で表し、直線や線分は複素ベクトルで考えることが基本戦略となります(空間幾何でもベクトルを使用します)。 複素ベクトルを使うと、頂点の回転などの一次変換や内積・外積が複素数の積で表せたり、方程式で直線・線分を表現したときに現れる例外ケースがベクトルには少ないなど、いくつかの利点があります。

具体的な実装方法については、ACM/ICPC国内予選突破の手引き平面幾何におけるベクトル演算というページが非常にわかりやすいので、このページを参考にしてください。 上記で挙げた「2つの線分が交差しているか」「多角形の面積はいくらか」という問題も、ベクトルの外積を使って簡単に解くことができます (具体的には線分の交差判定多角形の面積公式 - Wikipediaを参照)。

上記ページを見ればわかりますが、多角形の面積公式などの導出は自明なものではなく、プログラミングコンテストの競技時間中に一から導出することは困難です。かといって、主要な公式を片っ端から暗記するのは辛いです。

そこで、頻出の幾何計算はライブラリとして事前に用意しておくことをお勧めします。ライブラリを準備したからといっても内容を理解していなければ使いこなせませんが、幾何問題に対する思考時間を大きく短縮することができるはずです。 自分も上記ページやSpaghetti Sourceのほぼ丸写しですが幾何のライブラリを作成したので、よければご利用ください。

問題

秋田大学ICPC対策室@wiki - ライブラリ検証用問題も参考になります。