#include #include #include using namespace atcoder; using mint = modint1000000007; using namespace std; #define rep(i,n) for (int i = 0; i < (n); ++i) #define Inf 1000000001 template struct CHT{ deque> D; void add(T a,T b){ while(true){ if(D.size()<=1){ D.emplace_back(a,b); break; } T a3 = a,b3 = b,a2 = D.back().first,b2 = D.back().second; D.pop_back(); T a1 = D.back().first,b1 = D.back().second; D.pop_back(); if((a2-a1)*(b3-b2)>=(b2-b1)*(a3-a2)){ D.emplace_back(a1,b1); continue; } else{ D.emplace_back(a1,b1); D.emplace_back(a2,b2); D.emplace_back(a3,b3); break; } } } T query(T x,T y){ while(true){ if(D.size()<=1)break; T a1 = D.front().first,b1 = D.front().second; D.pop_front(); T a2 = D.front().first,b2 = D.front().second; if(a1*x+b1*y>=a2*x+b2*y){ continue; } else{ D.emplace_front(a1,b1); break; } } return D.front().first*x + D.front().second*y; } }; bool check(long long a0,long long b0,long long a1,long long b1,long long x,long long y){ return (a0-a1)*x < (b1-b0)*y; } int main(){ int n; cin>>n; vector> a(n); rep(i,n){ cin>>a[i].first>>a[i].second; swap(a[i].first,a[i].second); } sort(a.begin(),a.end()); CHT C; rep(i,n){ C.add(a[i].first,-a[i].second); } rep(i,n){ swap(a[i].first,a[i].second); } sort(a.begin(),a.end(),[](pair x,pair y){ return x.first*y.second