#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){ if(l.a==0 and l.b==0)os<<0; else if(l.a==0)os<0)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&l:lines)internal_push_back(l); } 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; } friend ostream&operator<<(ostream&os,const ConvexHullTrick&cht){ os<<"["; for(int i=0;i 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<>n; vector> xy(n); for(int i=0;i>xy[i]; sort(xy.begin(),xy.end()); MinConvexHullTrick CHT1; MaxConvexHullTrick CHT2; ld 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()){ ld res1=CHT1.query(v.y/v.x)*v.x, res2=CHT2.query(v.y/v.x)*v.x; chmax(ans, max(abs(res1),abs(res2))); } Line f(v.x,-v.y); CHT1.add(f); CHT2.add(f); } cout<