[ round-off error eps ] 浮點數誤差模板

有些計算幾何的過程中會產生捨位誤差，這時候就需要決定一個很小的數，去避開這個捨位誤差問題，我們稱那個很小的數為EPS

• A < B ....... A - B < - EPS
• A > B ....... A - B > EPS
• A == B ....... abs(A - B) <= EPS
• A <= B ....... A - B <= EPS
• A >= B ....... A - B >= - EPS

因為我的計算幾何模板在實作時是用template實作的，所以如果需要處理浮點數誤差時，需要傳入一個新的資料結構，所以寫了這份模板

	#ifndef SUNMOON_DOUBLE
	#define SUNMOON_DOUBLE
	#include <cmath>
	#include <iostream>
	const double EPS = 1e-9;
	struct Double {
	double d;
	Double(double d = 0) : d(d) {}
	Double operator-() const { return -d; }
	Double operator+(const Double &b) const { return d + b.d; }
	Double operator-(const Double &b) const { return d - b.d; }
	Double operator*(const Double &b) const { return d * b.d; }
	Double operator/(const Double &b) const { return d / b.d; }
	Double operator+=(const Double &b) { return d += b.d; }
	Double operator-=(const Double &b) { return d -= b.d; }
	Double operator*=(const Double &b) { return d *= b.d; }
	Double operator/=(const Double &b) { return d /= b.d; }
	bool operator<(const Double &b) const { return d - b.d < -EPS; }
	bool operator>(const Double &b) const { return d - b.d > EPS; }
	bool operator==(const Double &b) const { return fabs(d - b.d) <= EPS; }
	bool operator!=(const Double &b) const { return fabs(d - b.d) > EPS; }
	bool operator<=(const Double &b) const { return d - b.d <= EPS; }
	bool operator>=(const Double &b) const { return d - b.d >= -EPS; }
	friend std::ostream &operator<<(std::ostream &os, const Double &db) {
	return os << db.d;
	}
	friend std::istream &operator>>(std::istream &is, Double &db) {
	return is >> db.d;
	}
	};
	#endif

view raw eps.cpp hosted with ❤ by GitHub

[ long long multiply long long mod long long ] long long 乘 long long 模 long long不溢位算法

這標題有點長，不過也很清楚的顯示了這篇的重點，所以就直接附模板吧
如果a,b<m的話a%=m,b%=m;可以拿掉沒關係

code(比較慢，但適用範圍更大，算法取自維基百科:同餘):

	using ull = unsigned long long;
	ull _mod_mul(ull a,ull b,ull m){
	a%=m,b%=m;
	ull ans=0;
	for(;b;b>>=1){
	if(b&1){
	ans+=a;
	if(ans>=m)ans-=m;
	}
	a<<=1;
	if(a>=m)a-=m;
	}
	if(ans>=m)ans-=m;
	else if(ans<0)ans+=m;
	return ans;
	}

view raw mod_mul1.cpp hosted with ❤ by GitHub

[ Maze generation-Randomized Kruskal's algorithm ] 迷宮生成-隨機Kruskal算法

說得通俗點，就是"隨機拆牆"。
一開始假設所有牆都在，也就是圖的每個點都不連通。如果當前不滿足“任意兩個格子間都有唯一路徑”，那麼就隨機選擇一堵牆，要求牆兩端的格子不連通，即它們對應的兩個頂點在兩個不同的連通分量。把這堵牆拆掉，即在後牆兩端的格子對應的頂點間建立一條邊。重複作下去，直到所有的點都在同一個連通分量裡面。
會發現這就是隨機合併點的Kruskal演算法，需要用到並查集

範例生成圖:
＃＃＃＃＃＃＃＃＃＃＃＃＃＃＃＃＃＃＃＃＃＃＃＃＃
＃　　　＃　　　　　　　＃　　　＃　　　　　　　＃
＃＃＃　＃　＃　＃　＃＃＃　＃＃＃＃＃＃＃　＃＃＃
＃　　　　　＃　＃　　　＃　　　＃　＃　　　　　＃
＃＃＃＃＃＃＃＃＃　＃＃＃　＃　＃　＃＃＃＃＃　＃
＃　　　　　　　＃　＃　　　＃　　　＃　　　　　＃
＃＃＃　＃＃＃　＃　＃　＃　＃＃＃　＃＃＃　＃＃＃
＃　　　＃　　　＃　　　＃　　　＃　　　　　　　＃
＃＃＃　＃　＃＃＃＃＃　＃＃＃　＃＃＃＃＃　＃＃＃
＃　　　＃　　　　　　　＃　＃　　　　　＃　＃　＃
＃＃＃＃＃＃＃　＃　＃＃＃　＃　＃＃＃＃＃＃＃　＃
＃　　　＃　＃　＃　　　＃　　　　　　　＃　＃　＃
＃　＃＃＃　＃＃＃　＃＃＃　＃　＃＃＃＃＃　＃　＃
＃　＃　　　　　＃　＃　　　＃　＃　＃　＃　＃　＃
＃　＃　＃＃＃　＃　＃＃＃　＃＃＃　＃　＃　＃　＃
＃　＃　＃　　　　　＃　　　＃　　　　　　　　　＃
＃　＃　＃＃＃　＃＃＃＃＃＃＃＃＃　＃　＃＃＃＃＃
＃　　　＃　　　＃　＃　＃　　　　　＃　　　＃　＃
＃＃＃＃＃＃＃　＃　＃　＃　＃　＃＃＃　＃＃＃　＃
＃　　　　　＃　　　　　　　＃　　　＃　　　　　＃
＃　＃　＃＃＃＃＃　＃＃＃＃＃＃＃＃＃　＃　＃＃＃
＃　＃　　　　　　　　　　　　　　　＃　＃　　　＃
＃＃＃　＃　＃　＃＃＃　＃　＃＃＃＃＃＃＃　＃＃＃
＃　　　＃　＃　　　＃　＃　　　＃　　　　　　　＃
＃＃＃＃＃＃＃＃＃＃＃＃＃＃＃＃＃＃＃＃＃＃＃＃＃

code(n,m必須是奇數):

	#include<bits/stdc++.h>
	using namespace std;
	struct P{
	P(int q,int w,int e,int r):a(q),b(w),x(e),y(r){}
	int a,b;
	int x,y;
	};
	char s[105][105];
	int id[105][105],cnt;
	int st[10005];
	vector<P>p;
	inline int find(int x){
	return st[x]==x?x:st[x]=find(st[x]);
	}
	inline void print(int n,int m){
	for(int i=0;i<n;++i){
	for(int j=0;j<m;++j){
	if(s[i][j]=='#')printf("＃");
	else printf("　");
	}
	puts("");
	}
	}
	int main(){
	int n=25,m=25;
	for(int i=0;i<n;++i){
	for(int j=0;j<m;++j){
	s[i][j]='#';
	}
	}
	for(int i=1;i<n;i+=2){
	for(int j=1;j<m;j+=2){
	id[i][j]=++cnt;
	s[i][j]=' ';
	}
	}
	for(int i=1;i<n-1;++i){
	for(int j=1;j<m-1;++j){
	if(s[i][j]=='#'){
	if(s[i][j-1]!='#'&&s[i][j+1]!='#'){
	p.push_back(P(id[i][j-1],id[i][j+1],i,j));
	}else if(s[i-1][j]!='#'&&s[i+1][j]!='#'){
	p.push_back(P(id[i-1][j],id[i+1][j],i,j));
	}
	}
	}
	}
	for(int i=1;i<=cnt;++i)st[i]=i;
	srand(time(0));
	random_shuffle(p.begin(),p.end());
	for(int i=0;i<(int)p.size();++i){
	if(find(p[i].a)!=find(p[i].b)){
	st[find(p[i].a)]=find(p[i].b);
	s[p[i].x][p[i].y]=' ';
	}
	}
	print(n,m);
	return 0;
	}

view raw random kruskal.cpp hosted with ❤ by GitHub

[ min-max heap ] 最小-最大堆

最小-最大堆(Min-Max Heaps)是一個完整二元樹。此二元樹是交替的階層方式呈現，分別為最小階層 ( min level ) 和最大階層 ( max level ) ，這裡實作樹根為最小鍵值。

最小-最大堆是一種堆積支援以下幾種操作:

1. 求最大值 - max()
2. 求最小值 - min()
3. 刪除最大值 - pop_max()
4. 刪除最小值 - pop_min()
5. 元素入堆 - push()

詳細演算法可以參考原始論文
Min-Max Heaps and Generalized Priority Queues

如果不懂敘述就看code吧
以下提供模板:

	#ifndef SUNMOON_MIN_MAX_HEAP
	#define SUNMOON_MIN_MAX_HEAP
	#include<vector>
	#include<algorithm>
	template<typename T,typename _Seq=std::vector<T>,typename _Compare=std::less<T> >
	class minmax_heap{
	_Seq s;
	_Compare cmp;
	bool is_min_level(size_t id){
	return !(std::__lg(++id)%2);
	}
	void TrickleDown(size_t id){
	if(is_min_level(id)) TrickleDownMin(id);
	else TrickleDownMax(id);
	}
	size_t get_min_descendant(size_t id){
	size_t res=(++id)*2-1;
	for(size_t i=2;i<=4;i*=2){
	for(size_t j=0;j<i;++j){
	int descendant=id*i+j-1;
	if(descendant>=s.size()) return res;
	if(cmp(s[descendant],s[res])){
	res=descendant;
	}
	}
	}
	return res;
	}
	void TrickleDownMin(size_t id){
	while((id+1)*2<=s.size()){
	size_t m=get_min_descendant(id);
	if(cmp(s[m],s[id])){
	std::swap(s[m],s[id]);
	if(m<=(id+1)*2) return;
	if(cmp(s[(m+1)/2-1],s[m])){
	std::swap(s[(m+1)/2-1],s[m]);
	}
	id=m;
	}else return;
	}
	}
	size_t get_max_descendant(size_t id){
	size_t res=(++id)*2-1;
	for(size_t i=2;i<=4;i*=2){
	for(size_t j=0;j<i;++j){
	int descendant=id*i+j-1;
	if(descendant>=s.size()) return res;
	if(cmp(s[res],s[descendant])){
	res=descendant;
	}
	}
	}
	return res;
	}
	void TrickleDownMax(size_t id){
	while((id+1)*2<=s.size()){
	size_t m=get_max_descendant(id);
	if(cmp(s[id],s[m])){
	std::swap(s[m],s[id]);
	if(m<=(id+1)*2) return;
	if(cmp(s[m],s[(m+1)/2-1])){
	std::swap(s[(m+1)/2-1],s[m]);
	}
	id=m;
	}else return;
	}
	}
	void BubbleUp(size_t id){
	if(!id) return;
	int parent=(id+1)/2-1;
	if(is_min_level(id)){
	if(cmp(s[parent],s[id])){
	std::swap(s[parent],s[id]);
	BubbleUpMax(parent);
	}else BubbleUpMin(id);
	}else{
	if(cmp(s[id],s[parent])){
	std::swap(s[parent],s[id]);
	BubbleUpMin(parent);
	}else BubbleUpMax(id);
	}
	}
	void BubbleUpMin(size_t id){
	while(id>2){
	int grandparent=(id+1)/4-1;
	if(cmp(s[id],s[grandparent])){
	std::swap(s[id],s[grandparent]);
	id=grandparent;
	}else break;
	}
	}
	void BubbleUpMax(size_t id){
	while(id>2){
	int grandparent=(id+1)/4-1;
	if(cmp(s[grandparent],s[id])){
	std::swap(s[id],s[grandparent]);
	id=grandparent;
	}else break;
	}
	}
	size_t find_max_id()const{
	size_t res=0,n=std::min(s.size(),size_t(3));
	while(--n) if(cmp(s[res],s[n])) res=n;
	return res;
	}
	void erase_id(size_t id){
	s[id]=s.back();
	s.pop_back();
	TrickleDown(id);
	}
	public:
	bool empty()const{
	return s.empty();
	}
	int size()const{
	return s.size();
	}
	void push(const T&data){
	s.push_back(data);
	BubbleUp(s.size()-1);
	}
	const T&max()const{
	return s[find_max_id()];
	}
	const T&min()const{
	return s[0];
	}
	void pop_max(){
	erase_id(find_max_id());
	}
	void pop_min(){
	erase_id(0);
	}
	};
	#endif

view raw minmax_heap.cpp hosted with ❤ by GitHub