線分の交差判定 c++ Judgment of intersection of line segments

幾何ライブラリ

http://perogram.hateblo.jp/entry/abc016_4 この記事を関数として切り出した ※1番上のを安易に使うと誤判定する場合があります関数（追記：❌） // 交差判定セット typedef complex<double> C; double cross(C a, C b){ return a.real() * b.imag() - a.imag() * b.</double>…

2019-04-26

No.658 テトラナッチ数列 Hard 〜行列ライブラリのはじまり〜

ライブラリフィボナッチ行列繰り返し二乗法

Quiz https://yukicoder.me/problems/no/658 AC https://yukicoder.me/submissions/342366 解法公式解説の通りコンパイル vector<vector > を初期化子リストで初期化するにはオプションが必要 g++ -std=c++11 answer.cpp その他行列ライブラリと言えるほどではない</vector>…

2019-04-15

累積和クラスを作ってみた

ライブラリ累積和

作成動機元となる配列サイズ+1で作ったり、範囲の和を取る時に添え字でミスりそういつも同じ作成をしているので省略したい Code struct AccSum{ vector<ll> Ac; ll L; AccSum(vector<ll> &A){ L = A.size(); Ac.resize(L+1); FOR(i, 0, L){ Ac[i+1] = Ac[i] + A[i]</ll></ll>…

2019-03-29

素因数分解, 約数の種類数, 高速版 osa_k ～高速な素因数分解～

約数約数列挙ライブラリ素因数分解

O(√N) Ver // 素因数分解 // その素因数が何個あるかのmapを返す map<ll, ll> factorize(ll n){ map<ll, ll> mp; ll sq = sqrt(n); FOR(i, 2, sq+1){ while(n%i==0){ mp[i]++; n/=i; } } // 残り if(n!=1){ mp[n]++; } return mp; } // 約数の種類数 // 6 => 1, 2, 3, 6なの</ll,></ll,>…

2019-02-20

D - 閉路 abc014_4 ～木の深さを求めるdfs～

ライブラリダブリング LCA

Quiz https://atcoder.jp/contests/abc014/tasks/abc014_4 Submit https://atcoder.jp/contests/abc014/submissions/4325911 根が0決め打ちなので注意解法どこかをrootにしてdfsでdepthを測っておく LCA (Lowest Common Ancestor)が高速に求まれば、depth…

2019-01-25

LISとLCS D - トランプ挿入ソート (abc006_4)

ライブラリ

LCS (Longest Common Subsequence) 文字列s, tの最長の共通部分を見つける naoyaさんの記事が分かりやすい http://d.hatena.ne.jp/naoya/20090328/1238251033 DPで解く計算量O(N*M) // LCSセット const int S_LEN_MAX = 6000; ll dp[S_LEN_MAX][S_LEN_MAX];…