#include // https://github.com/hitonanode/cplib-cpp/blob/master/rational/rational_number.hpp template struct rational { constexpr rational(T num = 0, T den = 1) : p(num), q(den) { normalize(); } constexpr bool is_finite() const { return q != 0; } constexpr bool is_infinite() const { return p != 0 && q == 0; } constexpr bool is_nan() const { return p == 0 && q == 0; } constexpr rational &operator+=(const rational &o) { if (is_nan() || o.is_nan()) return *this = rational(0, 0); if (is_infinite() && o.is_infinite()) return *this = rational(p + o.p, 0); return *this = rational(p * o.q + q * o.p, q * o.q); } constexpr rational &operator-=(const rational &o) { if (is_nan() || o.is_nan()) return *this = rational(0, 0); if (is_infinite() && o.is_infinite()) return *this = rational(p - o.p, 0); return *this = rational(p * o.q - q * o.p, q * o.q); } constexpr rational &operator*=(const rational &o) { return *this = rational(p * o.p, q * o.q); } constexpr rational &operator/=(const rational &o) { if (o.p < 0) return *this = rational(p * -o.q, -q * o.p); return *this = rational(p * o.q, q * o.p); } friend constexpr rational operator+(rational a, const rational &b) { return a += b; } friend constexpr rational operator-(rational a, const rational &b) { return a -= b; } friend constexpr rational operator*(rational a, const rational &b) { return a *= b; } friend constexpr rational operator/(rational a, const rational &b) { return a /= b; } constexpr rational operator-() const { return rational(-p, q); } constexpr rational abs() const { return rational(0 < p ? p : -p, q); } constexpr T floor() const { assert(is_finite()); return floor_div(p, q); } constexpr T ceil() const { assert(is_finite()); return ceil_div(p, q); } constexpr std::partial_ordering operator<=>(const rational &r) const { if (is_nan() || r.is_nan()) { return std::partial_ordering::unordered; } if (is_infinite() && r.is_infinite()) { return p <=> r.p; } if (is_infinite()) { return p < 0 ? std::partial_ordering::less : std::partial_ordering::greater; } if (r.is_infinite()) { return r.p < 0 ? std::partial_ordering::greater : std::partial_ordering::less; } using W = std::conditional_t; return (W(p) * r.q) <=> (W(r.p) * q); } constexpr bool operator==(const rational &r) const { return (*this <=> r) == 0; } constexpr explicit operator double() const { return (double)p / (double)q; } constexpr explicit operator long double() const { return (long double)p / (long double)q; } constexpr T numerator() const { return p; } constexpr T denominator() const { return q; } private: constexpr void normalize() { if (q == 0) { p = (p > 0) - (p < 0); return; } if constexpr (reduce) { T g = __gcd(p, q); if (g) { p /= g; q /= g; } } if (q < 0) { p = -p; q = -q; } } T p, q; // 0 <= q }; // https://github.com/kth-competitive-programming/kactl/blob/main/content/data-structures/LineContainer.h template struct line_container { struct line { T a, b; mutable rational p; bool operator<(const line &o) const { return a < o.a; } bool operator<(auto x) const { return p < x; } }; static constexpr auto inf = rational(1, 0); bool isect(auto x, auto y) { if (y == lines.end()) { x->p = inf; return false; } if (x->a == y->a) { x->p = (y->b < x->b) ? inf : -inf; } else { x->p = rational(y->b - x->b, x->a - y->a); } return x->p >= y->p; } void add(T a, T b) { if constexpr (!maximize) { a = -a; b = -b; } auto z = lines.emplace(a, b, 0); auto y = z++; auto x = y; while (isect(y, z)) { z = lines.erase(z); } if (x != lines.begin() && isect(--x, y)) { y = lines.erase(y); isect(x, y); } while ((y = x) != lines.begin() && (--x)->p >= y->p) { isect(x, lines.erase(y)); } } std::pair query_line(auto x) const { assert(!lines.empty()); auto l = lines.lower_bound(x); if constexpr (maximize) { return {l->a, l->b}; } else { return {-l->a, -l->b}; } } T query(T x) const { auto [a, b] = query_line(x); return a * x + b; } private: std::multiset> lines; }; template struct line_container_2d { void add(T a, T b) { min_a = std::min(min_a, a); max_a = std::max(max_a, a); min_lc.add(a, b); max_lc.add(a, b); } T max(T x, T y) const { if (y == 0) { return x < 0 ? x * min_a : x * max_a; } rational r(x, y); auto [a, b] = (y < 0 ? min_lc.query_line(r) : max_lc.query_line(r)); return a * x + b * y; } T min(T x, T y) const { return -max(-x, -y); } static constexpr auto inf = std::numeric_limits::max(); T min_a = inf, max_a = -inf; line_container min_lc; line_container max_lc; }; int main() { std::cin.tie(0)->sync_with_stdio(0); int N; std::cin >> N; std::vector> P(N); line_container_2d lc; for (auto &[x, y] : P) { std::cin >> x >> y; lc.add(x, y); } auto ans = 0LL; for (auto [x, y] : P) { ans = std::max({ans, lc.max(y, -x), lc.max(-y, x)}); } std::cout << ans << "\n"; }