平面幾何問題

gistfile1.txt

ICPCのための平面幾何問題について学んだこと

基本は「点」。点はx座標y座標がわかればよい。
また、点があればベクトルを考えられる。ベクトルは原点からある点までの有向線分なので、点が一つあればベクトルを表現できる。
円は点と半径がわかればいい。
線分や直線は、それを通る点の対で表す。ただ、pairを使うのでなく、vectorを使った方が良いらしい。for文で端点をすべて回れたり、辞書準比較の演算子が最初からあるためらしい。
単純多角形はvectorで表現。ただ、その多角形が反時計回りなのか時計回りなのかか決めておかないといけない。

ベクトル計算のためには、ベクトルの加減算、スカラー倍、内積、外積が計算できると便利。
自分でstruct pointとか定義してメソッド定義するんでも良いけれど、複素数クラスで加減算とスカラー倍まではデフォルトでできるので、それで代用する。
あとは自分で複素数クラス使った内積、外積の関数を書けばよい。
ちなみにcomplexクラスはテンプレートをとるので、int型でもdouble型でもいける。（complex<int>, complex<double>とかする）

complexクラスを使うときは、実部にx座標、虚部にy座標を入れるのが定番。この順番を逆にすると内積、外積の定義が変わっちゃうので注意。
ということで、点aの座標を取り出す方法とセットする方法。
取り出し
x = a.real();
y = a.imag();
挿入（どっちの方法でも行けるらしい）
a.real(x);
a.real() = x
a.imag(y);
a.imag() = y;

二つのベクトルが等しいかどうかは、同じ座標にある点であるかどうかを判別すればいい。
ただし、double型とかだと単純に==で比較できないので（丸め誤差のせい）、小さな値EPSを1e-10とかって定義しておいて、座標値の差がEPS以下ならば等しい、とかする必要がある。

（引用：http://www.deqnotes.net/acmicpc/2d_geometry/using_vectors）
#define EPS (1e-10)
#define EQ(a,b) (abs((a)-(b)) < EPS)
#define EQV(a,b) ( EQ((a).real(), (b).real()) && EQ((a).imag(), (b).imag()) )

単なる大小比較なら、こういう演算子をオーバーロードしておけば楽にできる。（どちらの点の方が原点に近いか判別できる）
（引用：http://www.prefield.com/algorithm/geometry/geometry.html）
namespace std {
  bool operator < (const P& a, const P& b) {
    return real(a) != real(b) ? real(a) < real(b) : imag(a) < imag(b);
  }
}

ベクトルの絶対値をとるには、complex用のabs()をそのまま使えばいい。
ただしこれは内部でsqrtを使ってるため遅い。平方根とらないで計算したい場合は自力でx^2+y^2を計算すること。
単位ベクトルは
u = a / abs(a);
で求まる。
法線ベクトルを求めたければ、複素数の積の性質（複素数同士の積の結果は，「代数的には絶対値は積，偏角は和」）より、
P n1 = a * P(0, 1);
P n2 = a * P(0, -1);
で求まる。なお、一次元直線の法線は二本あることに注意。

ベクトルa, bがあるとき、その内積は
dot = a.real() * b.real() + a.imag() * b.imag();
もしくは
dot = imag(conj(a)*b);
（極座標変換とか面倒でやってないけど、これで行けるらしい。conj()は複素共役をとる関数）

引用元.txt

http://www.prefield.com/algorithm/geometry/geometry.html
http://www.deqnotes.net/acmicpc/2d_geometry/