#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 using ll = long long; struct F { ll a, b; F(ll a, ll b) : a(a), b(b) {} }; struct ConvexHullTrick { deque deq; bool check(F &f1, F &f2, F &f3) { return (f2.a - f1.a) * (f3.b - f2.b) >= (f2.b - f1.b) * (f3.a - f2.a); } ll f(F &f1, ll x,long long y) { return f1.a * x + f1.b*y; } public: // a_{prev} >= a void add_line(ll a, ll b) { F f1 = F(a, b); while(deq.size() >= 2 && check(deq[deq.size()-2], deq[deq.size()-1], f1)) { deq.pop_back(); } deq.push_back(f1); } // x_{prev} <= x ll query(ll x,ll y) { while(deq.size() >= 2 && f(deq[0], x, y) >= f(deq[1], x, y)) { deq.pop_front(); } return f(deq[0], x, 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()); ConvexHullTrick C; rep(i,n){ C.add_line(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