平面幾何の基本要素

説明

数値型

幾何学的な問題に対しては，常に浮動小数点型 double を用いることにする．整数座標に関する問題も浮動小数点で扱い，EPS を適当に設定することで対処することにする．

点

点はナイーブには座標の対であるが，加減算やスカラー倍が定義されていたほうが扱いやすい．そこで typedef complex<double> P; を用いることにする．

complex<number> の特徴は以下のとおり．

• x 座標は p.real(), real(p), y 座標は p.imag(), imag(p) とする．
• 足し算，引き算，スカラー倍は定義済み．
• operator < は入っていないので自分で namespace std に突っ込む．

幾つかのアルゴリズムが operator < に依存するので，一度決めたものを使い続けることが重要である．

線分，直線

線分，点ともにそれが通る二点を用いて表現する．そのための型として vector<P> を継承したものを作る．これにより

• 辞書順の比較演算子が定義済み．
• 端点を for で走れる．

などのメリットが得られる．

単純多角形

単純な（自己交差の無い）多角形は頂点のリスト typedef vector<P> G であらわす．ほとんどのアルゴリズムは多角形が反時計回りであることを仮定する．

円

円は中心と半径の対であらわす．

ソースコード

const double EPS = 1e-8;
const double INF = 1e12;
typedef complex<double> P;
namespace std {
  bool operator < (const P& a, const P& b) {
    return real(a) != real(b) ? real(a) < real(b) : imag(a) < imag(b);
  }
}
double cross(const P& a, const P& b) {
  return imag(conj(a)*b);
}
double dot(const P& a, const P& b) {
  return real(conj(a)*b);
}

struct L : public vector<P> {
  L(const P &a, const P &b) {
    push_back(a); push_back(b);
  }
};

typedef vector<P> G;

struct C {
  P p; double r;
  C(const P &p, double r) : p(p), r(r) { }
};