convexhulltrick/linecontainer.cpp

• View this file on GitHub
• Last update: 2020-10-03 18:22:12+09:00

Verified with

• test MaxLineContainer (test/aoj/2725.linecontainer.test.cpp)
• test MinLineContainer (test/aoj/3069.test.cpp)

Code

#ifndef call_from_test
#include<bits/stdc++.h>
using namespace std;
#endif
//BEGIN CUT HERE
enum Objective{
  MAXIMIZE = +1,
  MINIMIZE = -1,
};

template<typename T>
struct Line {
  mutable T k,m,p;
  bool operator<(const Line&o)const{return k<o.k;}
  bool operator<(T x)const{return p<x;}
};

template<typename T> T lc_inf(){return numeric_limits<T>::max();}
template<> double lc_inf<double>(){return 1/.0;}

template<typename T> T lc_div(T a,T b){return a/b-((a^b)<0 and a%b);}
template<> double lc_div(double a,double b){return a/b;};

template<typename T, Objective objective>
struct LineContainer : multiset<Line<T>, less<>>{
  using super = multiset<Line<T>, less<>>;
  using super::begin,super::end,super::insert,super::erase;
  using super::empty,super::lower_bound;
  const T inf = lc_inf<T>();
  bool insect(typename super::iterator x,typename super::iterator y){
    if(y==end()) return x->p=inf,false;
    if(x->k==y->k) x->p=(x->m>y->m?inf:-inf);
    else x->p=lc_div(y->m-x->m,x->k-y->k);
    return x->p>=y->p;
  }
  void add(T k,T m){
    auto z=insert({k*objective,m*objective,0}),y=z++,x=y;
    while(insect(y,z)) z=erase(z);
    if(x!=begin() and insect(--x,y)) insect(x,y=erase(y));
    while((y=x)!=begin() and (--x)->p>=y->p) insect(x,erase(y));
  }
  T query(T x){
    assert(!empty());
    auto l=*lower_bound(x);
    return (l.k*x+l.m)*objective;
  }
};
template<typename T>
using MinLineContainer = LineContainer<T, Objective::MINIMIZE>;
template<typename T>
using MaxLineContainer = LineContainer<T, Objective::MAXIMIZE>;
//END CUT HERE

#ifndef call_from_test
//INSERT ABOVE HERE
signed main(){
  return 0;
}
#endif

#line 1 "convexhulltrick/linecontainer.cpp"

#include<bits/stdc++.h>
using namespace std;
#endif
//BEGIN CUT HERE
enum Objective{
  MAXIMIZE = +1,
  MINIMIZE = -1,
};

template<typename T>
struct Line {
  mutable T k,m,p;
  bool operator<(const Line&o)const{return k<o.k;}
  bool operator<(T x)const{return p<x;}
};

template<typename T> T lc_inf(){return numeric_limits<T>::max();}
template<> double lc_inf<double>(){return 1/.0;}

template<typename T> T lc_div(T a,T b){return a/b-((a^b)<0 and a%b);}
template<> double lc_div(double a,double b){return a/b;};

template<typename T, Objective objective>
struct LineContainer : multiset<Line<T>, less<>>{
  using super = multiset<Line<T>, less<>>;
  using super::begin,super::end,super::insert,super::erase;
  using super::empty,super::lower_bound;
  const T inf = lc_inf<T>();
  bool insect(typename super::iterator x,typename super::iterator y){
    if(y==end()) return x->p=inf,false;
    if(x->k==y->k) x->p=(x->m>y->m?inf:-inf);
    else x->p=lc_div(y->m-x->m,x->k-y->k);
    return x->p>=y->p;
  }
  void add(T k,T m){
    auto z=insert({k*objective,m*objective,0}),y=z++,x=y;
    while(insect(y,z)) z=erase(z);
    if(x!=begin() and insect(--x,y)) insect(x,y=erase(y));
    while((y=x)!=begin() and (--x)->p>=y->p) insect(x,erase(y));
  }
  T query(T x){
    assert(!empty());
    auto l=*lower_bound(x);
    return (l.k*x+l.m)*objective;
  }
};
template<typename T>
using MinLineContainer = LineContainer<T, Objective::MINIMIZE>;
template<typename T>
using MaxLineContainer = LineContainer<T, Objective::MAXIMIZE>;
//END CUT HERE

#ifndef call_from_test
//INSERT ABOVE HERE
signed main(){
  return 0;
}
#endif

Back to top page