Convex Hull Trick using STL::set

cht.cpp

// max cht (integer type query)
// Usage:
//  Insert: cht.insert({a,b})
//  Query:  cht.query(x)
struct CHT {
	using ll=__int128;
	using Line=pair<ll,ll>;
	using Point=pair<ll,Line>;
	const ll INF=1e15;
	set<Line> line_set;
	set<Point> point_set;
	inline Point getf(Line a,Line b) {
		if(b.fi>a.fi) return {(a.se-b.se)/(b.fi-a.fi)-((a.se-b.se)%(b.fi-a.fi)<0),b};
		return {(b.se-a.se)/(a.fi-b.fi)-((b.se-a.se)%(a.fi-b.fi)<0),b};
	}
	inline bool bad(Line a,Line b,Line c) {
		return getf(b,c)<=getf(a,b);
	}
	void _add(Line ln) {
		auto it=line_set.lower_bound(ln);
		if(it!=line_set.end()) {
			if(it==line_set.begin()) point_set.erase({-INF,*it});
			else point_set.erase(getf(*prev(it,1),*it));
			point_set.insert(getf(ln,*it));
		}
		if(it!=line_set.begin())
			point_set.insert(getf(*prev(it,1),ln));
		else point_set.insert({-INF,ln});
		line_set.insert(ln);
	}
	set<Line>::iterator _erase(set<Line>::iterator it) {
		if(it!=line_set.begin())
			point_set.erase(getf(*prev(it,1),*it));
		else point_set.erase({-INF,*it});
		if(next(it,1)!=line_set.end()) {
			point_set.erase(getf(*it,*next(it,1)));
			if(it!=line_set.begin())
				point_set.insert(getf(*prev(it,1),*next(it,1)));
		}
		return line_set.erase(it);
	}
	void insert(Line newline) {
		auto it=line_set.lower_bound({newline.fi,-INF});
		if(it!=line_set.end()&&it->fi==newline.fi) {
			if(it->se<newline.se) it=_erase(it);
			else return;
		}
		if(it!=line_set.end()&&it!=line_set.begin()&&bad(*prev(it,1),newline,*it))
			return;
		if(it!=line_set.begin()) {
			auto jt=prev(it,1);
			while(jt!=line_set.begin()&&bad(*prev(jt,1),*jt,newline)) {
				jt=_erase(jt);
				jt--;
			}
		}
		while(it!=line_set.end()&&next(it,1)!=line_set.end()&&bad(newline,*it,*next(it,1)))
			it=_erase(it);
		_add(newline);
	}
	ll query(ll x) {
		auto it=point_set.lower_bound({x,{-INF,-INF}});
		if(it==point_set.begin()) return -INF;
		it--;
		return (it->se.fi)*x+(it->se.se);
	}
};

cht_double.cpp

// max cht (double type query)
// Usage:
//  Insert: cht.insert({a,b})
//  Query:  cht.query(x)
struct CHT {
	using ll=__int128;
	using ld=double;
	using line=pair<ll,ll>;
	const ll INF=1e15;
	struct Point {
		ll n,d;
		line ln;
		Point(){}
		Point(ll n,ll d,line ln):n(n),d(d),ln(ln){}
		bool operator<=(const Point& b)const {
			ll v=n*b.d-b.n*d;
			if((b.d>0)^(d>0)) return v>=0;
			return v<=0;
		}
	};
	struct Point_cmp {
		using is_transparent=void;
		bool operator()(const Point& a,const Point& b)const {
			//a.n*b.d<a.d*b.n;
			ll v=a.n*b.d-a.d*b.n;
			if((a.d>0)^(b.d>0)) return v>0;
			return v<0;
		}
		bool operator()(const Point& a,ld x)const {
			//n<d*x
			ld v=(ld)a.n-(ld)a.d*x;
			if(a.d<0) return v>0;
			return v<0;
		}
		bool operator()(ld x,const Point& a)const {
			ld v=(ld)a.d*x-(ld)a.n;
			if(a.d<0) return v>0;
			return v<0;
		}
	};
	set<Line> line_set;
	set<Point,Point_cmp> point_set;
	inline Point getf(Line a,Line b) {
		Point f;
		f.n=a.se-b.se;
		f.d=b.fi-a.fi;
		f.ln=b;
		return f;
	}
	inline bool bad(Line a,Line b,Line c) {
		return getf(b,c)<=getf(a,b);
	}
	void _insert(Line ln) {
		auto it=line_set.lower_bound(ln);
		if(it!=line_set.end()) {
			if(it==line_set.begin()) point_set.erase(Point(-INF,1,*it));
			else point_set.erase(getf(*prev(it,1),*it));
			point_set.insert(getf(ln,*it));
		}
		if(it!=line_set.begin())
			point_set.insert(getf(*prev(it,1),ln));
		else point_set.insert(Point(-INF,1,ln));
		line_set.insert(ln);
	}
	set<Line>::iterator _erase(set<Line>::iterator it) {
		if(it!=line_set.begin())
			point_set.erase(getf(*prev(it,1),*it));
		else point_set.erase(Point(-INF,1,*it));
		if(next(it,1)!=line_set.end()) {
			point_set.erase(getf(*it,*next(it,1)));
			if(it!=line_set.begin())
				point_set.insert(getf(*prev(it,1),*next(it,1)));
		}
		return line_set.erase(it);
	}
	void insert(Line newline) {
		auto it=line_set.lower_bound({newline.fi,-INF});
		if(it!=line_set.end()&&it->fi==newline.fi) {
			if(it->se<newline.se) it=_erase(it);
			else return;
		}
		if(it!=line_set.end()&&it!=line_set.begin()&&bad(*prev(it,1),newline,*it))
			return;
		if(it!=line_set.begin()) {
			auto jt=prev(it,1);
			while(jt!=line_set.begin()&&bad(*prev(jt,1),*jt,newline)) {
				jt=_erase(jt);
				jt--;
			}
		}
		while(it!=line_set.end()&&next(it,1)!=line_set.end()&&bad(newline,*it,*next(it,1)))
			it=_erase(it);
		_insert(newline);
	}
	ld query(ld x) {
		auto it=point_set.lower_bound(x);
		if(it==point_set.begin()) return -INF;
		it--;
		return (ld)(it->ln.fi)*x+(ld)(it->ln.se);
	}
};