複素数演算による幾何ライブラリの実装 - ヘクトのメモ

この記事はMCC Advent Calendar 2016 15日目の記事です．ICPC向けの複素数演算による幾何ライブラリの実装について話します． MCC Advent Calendar 2016 - Adventar 遅れてすいません... 背景 ICPCでは幾何の問題が出てきます． ただし，ICPCでは電子的な事前準備の禁止と標準ライブラリしか使えない制約があります． このため，標準ライブラリ縛りで幾何に必要な関数を一から実装する必要があります． しかし，事前準備なしで幾何に必要な関数を実装するのは大変なことであり，多くのチームは紙媒体でライブラリを用意していると思います． 幾何に必要な関数を一から実装するとコード量も膨大になりがちです． そこで，複素数演算を活用することで実装量を減らすことができます． (ただし，2D限定です．あと，事実だけを淡々と書いていきます．) ベクトル 2次