#define PROBLEM "https://yukicoder.me/problems/no/2012" #include using namespace std; template struct Line{ T a,b; Line()=default; Line(T a,T b):a(a),b(b){} Line(pair l):a(l.first),b(l.second){} Line(T c):a(0),b(c){} T operator()(const T x)const{ return a*x+b; } Line operator()(const Line&l)const{ return Line(a*l.a, a*l.b+b); } bool operator==(const Line&l)const{ return a==l.a and b==l.b; } bool operator!=(const Line&l)const{ return !(*this == l); } bool operator<(const Line&l)const{ return (a==l.a ? a>(istream&is,Line&l){ is>>l.a>>l.b; return is; } friend ostream&operator<<(ostream&os,const Line&l){ os< class ConvexHullTrick:deque>{ using L=Line; using deque::back; using deque::front; using deque::push_back; using deque::push_front; using deque::pop_back; using deque::pop_front; using deque::at; static bool check(const L&l1,const L&l2,const L&l3){ return (l2.b-l1.b)*(l2.a-l3.a) >= (l3.b-l2.b)*(l1.a-l2.a); } void internal_push_back(const L&l){ if(size()){ if(back().a == l.a){ if(back().b <= l.b)return; else pop_back(); } while(size() >= 2){ L l1 = at(size()-2), l2 = back(); if(check(l1,l2,l))pop_back(); else break; } } push_back(l); } void internal_push_front(const L&l){ if(size()){ if(front().a == l.a){ if(front().b >= l.b)return; else pop_front(); } while(size() >= 2){ L l2 = at(0), l3 = at(1); if(check(l,l2,l3))pop_front(); else break; } } push_front(l); } public: using value_type = L; using deque::size; ConvexHullTrick()=default; ConvexHullTrick(vector lines){ if(OBJ==-1)for(auto&l:lines)l=-l; sort(lines.begin(),lines.end()); for(const auto&[a,b]:lines)internal_push_back(a,b); } void add(L l){ if(OBJ==-1)l=-l; if(!size() or back().a >= l.a)internal_push_back(l); else if(l.a >= front().a)internal_push_front(l); else assert(false); } void add(T a,T b){ add(L(a,b)); } T query(T x)const{ assert(size()); int l=-1,r=size()-1; while(r-l>1){ int m=(l+r)>>1; (at(m)(x)>=at(m+1)(x) ? l : r)=m; } return at(r)(x)*OBJ; } T query_monotone_inc(T x){ assert(size()); while(size()>=2 and at(0)(x)>=at(1)(x)) pop_front(); return at(0)(x)*OBJ; } T query_monotone_dec(T x){ assert(size()); while(size()>=2 and at(size()-2)(x)<=back()(x)) pop_back(); return back()(x)*OBJ; } vector query(const vector&xs){ int n=xs.size(); vector idx(n); iota(idx.begin(),idx.end(),0); sort(idx.begin(),idx.end(),[&](int i,int j){ return xs[i] ans(n); for(int id:idx)ans[id]=query_monotone_inc(xs[id]); return ans; } }; } template using MinConvexHullTrick = convex_hull_trick::ConvexHullTrick; template using MaxConvexHullTrick = convex_hull_trick::ConvexHullTrick; template struct XY{ T x,y; XY()=default; XY(T x,T y):x(x),y(y){} XY operator+()const{ return *this; } XY operator-()const{ return XY(-x,-y); } XY& operator++(){ x++;y++;return *this; } XY& operator--(){ x--;y--;return *this; } XY& operator++(int){ XY a=*this; ++*this; return a; } XY& operator--(int){ XY a=*this; --*this; return a; } XY& operator+=(const XY& v){ x+=v.x; y+=v.y; return *this; } XY& operator-=(const XY& v){ x-=v.x; y-=v.y; return *this; } XY& operator*=(const T& a){ x*=a; y*=a; return *this; } XY& operator/=(const T& a){ x/=a; y/=a; return *this; } friend XY operator+(const XY& u,const XY& v){ return XY(u)+=v; } friend XY operator-(const XY& u,const XY& v){ return XY(u)-=v; } friend XY operator*(const XY&u,const T& a){ return XY(u)*=a; } friend XY operator*(const T& a,const XY&u){ return XY(u)*=a; } friend XY operator/(const XY&u,const T& a){ return XY(u)/=a; } bool operator<(const XY&v)const{ return x!=v.x ? x(const XY&v)const{ return x!=v.x ? x>v.x : y>v.y; } bool operator==(const XY&v)const{ return x==v.x and y==v.y; } bool operator!=(const XY&v)const{ return !(*this==v); } double arg()const{ return atan2(y,x); } friend T dot(const XY&u,const XY& v){ return u.x*v.x + u.y*v.y; } T norm(){ return dot(*this,*this); } T abs(){ return sqrt(norm()); } friend istream&operator>>(istream&is,XY&v){ is>>v.x>>v.y; return is; } friend ostream&operator<<(ostream&os,const XY&v){ os< struct Fraction{ T num,den; Fraction(T n=0,T d=1):num(n),den(d){ assert(den!=0); if(den<0)num=-num,den=-den; T g=gcd(abs(num),abs(den)); num/=g; den/=g; } Fraction operator+(const Fraction& b)const{ return Fraction( num*b.den + den*b.num, den*b.den ); } Fraction operator-(const Fraction& b)const{ return Fraction( num*b.den - den*b.num, den*b.den ); } Fraction operator*(const Fraction& b)const{ return Fraction( num*b.num, den*b.den ); } Fraction operator/(const Fraction& b)const{ return Fraction( num*b.den, den*b.num ); } Fraction& operator+=(const Fraction& b){ return *this = (*this) + b; } Fraction& operator-=(const Fraction& b){ return *this = (*this) - b; } Fraction& operator*=(const Fraction& b){ return *this = (*this) * b; } Fraction& operator/=(const Fraction& b){ return *this = (*this) / b; } Fraction operator+(const T&c)const{ return (*this)+Fraction(c,1); } Fraction operator-(const T&c)const{ return (*this)-Fraction(c,1); } Fraction operator*(const T&c)const{ return (*this)*Fraction(c,1); } Fraction operator/(const T&c)const{ return (*this)/Fraction(c,1); } friend Fraction operator+(const T&c, Fraction b){ return Fraction(c,1)+b; } friend Fraction operator-(const T&c, Fraction b){ return Fraction(c,1)-b; } friend Fraction operator*(const T&c, Fraction b){ return Fraction(c,1)*b; } friend Fraction operator/(const T&c, Fraction b){ return Fraction(c,1)/b; } Fraction& operator+=(const T&c){ return *this = (*this)+c; } Fraction& operator-=(const T&c){ return *this = (*this)-c; } Fraction& operator*=(const T&c){ return *this = (*this)*c; } Fraction& operator/=(const T&c){ return *this = (*this)/c; } Fraction& operator++(){ return (*this)+=1; } Fraction& operator--(){ return (*this)-=1; } Fraction& operator++(int){ return (*this)+=1; } Fraction& operator--(int){ return (*this)-=1; } Fraction operator+()const{ return *this; } Fraction operator-()const{ return Fraction(-num,den); } static Fraction raw(T a){ return Fraction(a,1); } Fraction pow(long long k)const{ Fraction res(1,1), tmp(*this); while(k){ if(k&1)res*=res; tmp*=tmp; k>>=1; } return res; } Fraction inv(){ return Fraction(den,num); } friend ostream& operator<<(ostream&os,const Fraction &a){os<>(istream&is,Fraction &a){ is>>a.num;a.den=1; return is;} #define define_cmp(op) \ bool operator op (const Fraction& b) const{ return num*b.den op b.num*den; } define_cmp(==) define_cmp(!=) define_cmp(<) define_cmp(>) define_cmp(<=) define_cmp(>=) #undef define_cmp }; using ll=long long; using F=Fraction; void chmax(ll&a,ll b){ if(a>n; vector> xy(n); for(int i=0;i>xy[i]; sort(xy.begin(),xy.end()); MinConvexHullTrick CHT1; MaxConvexHullTrick CHT2; ll ans=0; for(const auto&v:xy){ if(v.x==0){ chmax(ans,abs(xy[0].x * v.y)); chmax(ans,abs(xy.back().x * v.y)); continue; } if(CHT1.size()){ F res1=CHT1.query(F(v.y,v.x))*v.x, res2=CHT2.query(F(v.y/v.x))*v.x; assert(res1.den==1 and res2.den==1); chmax(ans, max(res1.num,res2.num)); } Line f(F(v.x),F(-v.y)); CHT1.add(f); CHT2.add(f); } cout<