競プロでは、ベクトルを扱う数学問題がよく出題されます。
本記事では、コピペで使えるベクトル構造体のライブラリをC++で実装します。
主な機能と計算量
| 名前 | 説明 | 計算量 |
|---|---|---|
constructor() |
(0,0) のベクトルを作る |
$O(1)$ |
constructor(x,y) |
(x,y) のベクトルを作る |
$O(1)$ |
manhat(v) |
v とのマンハッタン距離を返す |
$O(1)$ |
euclid(v) |
v とのユークリッド距離を返す |
$O(1)$ |
euclid2(v) |
v とのユークリッド距離の 2 乗を返す |
$O(1)$ |
rot_l_90 |
原点を中心に左に90度回転させる | $O(1)$ |
rot_l_90(v) |
v を中心に左に90度回転させる |
$O(1)$ |
rot_l(s) |
原点を中心に左に s 度回転させる（弧度法） |
$O(1)$ |
rot_l(v,s) |
v を中心に左に s 度回転させる（弧度法） |
$O(1)$ |
cross(v) |
自分と v の外積の大きさを計算（符号付き） |
$O(1)$ |
実装したコード
template<typename T> // 座標の型
struct Vec {
////////////メンバ変数///////////////
// - 通常の数学と同じように(x,y)座標系で考える
T x,y;
/////////////コンストラクタ/////////////
Vec(): x(T(0)), y(T(0)) {}
Vec(T x, T y): x(x), y(y) {}
////////演算子のオーバーロード/////////
// - 足し算、引き算に関しては各座標に対して行う
bool operator==(const Vec<T>& v) const { return tie(x, y) == tie(v.x, v.y); }
bool operator!=(const Vec<T>& v) const { return tie(x, y) != tie(v.x, v.y); }
Vec<T> operator+(const Vec<T>& v) const { return Vec<T>{x+v.x, y+v.y}; }
Vec<T> operator-(const Vec<T>& v) const { return Vec<T>{x-v.x, y-v.y}; }
Vec<T> operator*(T k) const { return Vec<T>(x*k, y*k); }
Vec<T> operator/(T k) const { return Vec<T>(x/k, y/k); }
////////メンバ関数↓///////////
//-------距離系--------
T manhat(const Vec<T>& v) const {
return abs(x - v.x) + abs(y - v.y);
}
double euclid(const Vec<T>& v) const {
return sqrt(euclid2(v));
}
T euclid2(const Vec<T>& v) const {
T dx = x - v.x;
T dy = y - v.y;
return dx*dx + dy*dy;
}
//---------回転系-----------
// - 角度指定は弧度法
// - 90度以外の回転は T=double 専用
void rot_l_90(){
T nx = -y;
T ny = x;
x = nx;
y = ny;
}
void rot_l_90(const Vec<T>& v){
Vec<T> t = *this - v; // v中心の座標空間での座標に変換
t.rot_l_90(); // そのまま90度回転
t = t + v; // 原点中心に戻す
*this = t;
}
void rot_l(double s){
T nx = x*cos(s) - y*sin(s);
T ny = x*sin(s) + y*cos(s);
x = nx;
y = ny;
}
void rot_l(const Vec<T>& v, double s){
Vec<T> t = *this - v; // v中心の座標空間での座標に変換
t.rot_l(s); // そのままs度回転
t = t + v; // 原点中心に戻す
*this = t;
}
//-----演算系------
T dot(const Vec<T>& v) const {
return x*v.x + y*v.y;
}
T cross(const Vec<T>& b) const {
return x*b.y - y*b.x;
}
//------デバッグ用------
friend ostream& operator<<(ostream& os, const Vec<T>& v){
return os << "(" << v.x << "," << v.y << ")";
}
};
//よく使う型のエイリアス
using Vecll = Vec<long long>;
using Veci = Vec<int>;
using Vecd = Vec<double>;
使用例
#include<bits/stdc++.h>
using namespace std;
//--------ここにVecライブラリ---------//
// //
//---------------------------------//
int main(void){
// ベクトルを作成
Vecll a(1,2), b(3,4);
// ユークリッド距離（の2乗）を計算
cout << a.euclid2(b) << endl; // 8
// 左に90度回転
a.rot_l_90();
cout << a << endl;
}
注意点・Tips
- 通常の
(x,y)-座標系を想定しているので、(i,j)-座標系などで扱う場合は適宜変更が必要です -
Tが整数型の場合、rot_lは、誤差によりズレることがあります