競技プログラミング? > C++ > STL > complex

---

---

複素数型

複素数型.
使うには, #include<complex> が必要.
std::complex<T> で, T を要素似持つ複素数クラスを使える.
すなわち, なる要素を扱える.
但し, T として有効なのは float, double, long double のみで, 他は未定義.

#include <complex>
#include <iostream>
using namespace std;
int main(void){
    complex<double> a(1, 0), i(0, 1);   //aは1+0\sqrt{-1}, iは0+1\sqrt{-1}
    cout << a * i * i + 1.0 << endl;    // => (0, 0)
    cout << conj(i) << endl;            // => (0, -1) : 共役
    cout << abs(a+i) << endl;           // => 1.41421 : 絶対値
    cout << norm(a+i) << endl;          // => 2       : 絶対値^2
    return 0;
}

---

平面幾何

complex は複素数型であるが, 競技プログラミングでは, 複素数を扱うより, むしろ二次元ベクトルとして利用する事が多い.
対応は, 複素平面を考えればわかるだろう.
但し, complex<double> + double のような操作も valid になってしまうので, コーディングミスに注意する必要がある.
平面幾何の基礎的な要素として, 内積と外積があるが, これらは, 複素数の積と, 共役を使うと簡単に書ける.

#include <complex>
#include <iostream>
using namespace std;
 
typedef complex<double> P;
#define X real()
#define Y imag()
 
double dot(P a, P b){
    return (a * conj(b)).X;
}
double cross(P a, P b){
    return (a * conj(b)).Y;
}
int main(void){
    P a(0, 1), b(20, 1);
    cout << dot(a, b) << endl;    //=>  1  : 内積
    cout << cross(a, -b) << endl; //=> -20 : 外戚ベクトルの(方向を含めた)大きさ.
    return 0;
}

---

格子

以下のは使っちゃダメ!!!!
普通, complex<T> の T って double 以外入れる余地ないだろという感じがするが, complex<int> も意外に使える.
格子点を動く問題や, ボードゲームでの駒の位置など, 2つの整数の組で表すものに使うと, pair<int, int> に比べ, 足し算があるなど, メリットもある.(デメリットもあるが.)
よく 隣合う点に移動出来る とか, 隣の点 系の問題があるが, (complexを使うか否かに限らず) 相対座標で隣の点を列挙しておくと便利である.
隣 の定義でよく用いられるのは十字型の4つ(四近傍とも)であるが, 斜めも入れた八近傍(将棋の王の動き)を考える場合もあり, その場合は P(±1, ±1)の4つを加えればよい.
また, を掛けると90度回転する事も覚えておくとよい.(複素平面で考えれば明らか).

#include <complex>
#include <iostream>
using namespace std;
 
typedef complex<int> P;
P dirs[] = { P(1, 0), P(0, 1), P(-1, 0), P(0, -1) };
// complexを使わない場合は, 例えば
// int dx[] = {1, 0, -1, 0};
// int dy[] = {0, 1, 0, -1};
// などとするとよい.
 
int main(void){
    P p(3, 0);
    for(int d = 0; d < 4; ++d){
        cout << (p + dirs[d]) << endl;
    }
}

---

比較演算子

complex には < が定義されていない(自然な順序が無い)ため, そのままでは set や map のキーとして使う事が出来ない.
キーにしたければ, 例えば次のように定義してやればよい.

#include <complex>
#include <iostream>
#include <set>
using namespace std;
 
namespace std{
    template<class T> bool operator<(const complex<T> &a, const complex<T> &b){
        return a.real() == b.real() ? a.imag() < b.imag() : a.real() < b.real();
    }
};
typedef complex<int> P;
#define X real()
#define Y imag()
int main(void){
    set<P> a;
    a.insert(P(1, 0));
    return 0;
}

編集