lower convex hull self-balancing binary search tree

convexBST.cpp

#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

test.cpp

#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;
}