[ lower convex hull self-balancing binary search tree ] 下凸包平衡樹

下凸包平衡樹是一個動態維護下凸包的資料結構，他至少能在$\ord{\log n}$時間完成以下兩個操作：

1. 查詢 point(x,y) 是否被包含於下凸包中
2. 將 point(x,y) 加入至下凸包中，然後將不位於下凸包頂點上的點刪除

由於繼承自C++ STL map，因此所有能對map用的操作都能被使用，對於那些會改動map資料的操作請小心使用避免影響到凸包的正確性，例如operator[]就盡量不要使用。

對於某些動態規劃問題需要用凸包斜率優化時應該非常有用，有空會補上專門用來動態做斜率優化的版本

	#include<map>
	using std::map;
	using std::pair;
	#define x first
	#define y second
	template<typename T>
	class convexBST : public map<T,T>{
	typedef const pair<T,T>& point;
	static T cross(point a, point b, point c){
	return (a.x-c.x) * (b.y-c.y) - (b.x-c.x) * (a.y-c.y);
	}
	public:
	bool isIn(point p)const{
	if(this->empty()) return 0;
	if(this->count(p.x)) return p.y >= this->at(p.x);
	if(p.x < this->begin()->x || (--this->end())->x < p.x) return 0;
	auto l = this->lower_bound(p.x), r = l--;
	return cross(*r,p,*l)>=0;
	}
	void add(point p){
	if(isIn(p)) return;
	(*this)[p.x] = p.y;
	auto l = this->upper_bound(p.x), r = l--;
	if(r!=this->end())
	for(auto r2 = r++; r!=this->end(); r2=r++){
	if(cross(*r2,*r,p)>0) break;
	this->erase(r2);
	}
	if(l!=this->begin()&&--l!=this->begin())
	for(auto l2 = l--; l2!=this->begin(); l2=l--){
	if(cross(*l,*l2,p)>0) break;
	this->erase(l2);
	}
	}
	};
	#undef x
	#undef y

view raw convexBST.cpp hosted with ❤ by GitHub

	#include<bits/stdc++.h>
	using namespace std;
	int main(){
	convexBST<int> hull;
	vector<pair<int,int>> pointSet={{0,-1},{0,1},{-1,-5},{6,4},{-8,8}};
	for(auto p:pointSet)
	hull.add(p);
	printf("Points on the lower convex hull:");
	for(auto p:hull)
	printf(" (%d,%d)",p.first,p.second);
	puts("");
	puts(hull.isIn({6,0}) ? "Point(6,0) is in." : "Point(6,0) isn\'t in.");
	puts(hull.isIn({1,1}) ? "Point(1,1) is in." : "Point(1,1) isn\'t in.");
	return 0;
	}

view raw test.cpp hosted with ❤ by GitHub