#include using namespace std; // clang-format off using i8 = signed char; using u8 = unsigned char; using i32 = int; using u32 = unsigned; using i64 = long long; using u64 = unsigned long long; using i128 = __int128; using u128 = unsigned __int128; template T ceil_div(T a, T b) { return a / b + static_cast((a ^ b) > 0 && a % b != 0); } template T floor_div(T a, T b) { return a / b - static_cast((a ^ b) < 0 && a % b != 0); } template void read(auto &a) { for (auto &x : a) { cin >> x; if constexpr (I) { x -= I; } } } template void show(const auto &a, string_view sep = " ", string_view end = "\n") { for (auto it = a.begin(); it != a.end(); ++it) { if (it != a.begin()) { cout << sep; } auto x = *it; if constexpr (I) { x += I; } cout << x; } cout << end; } // clang-format on // 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 partial_ordering::unordered; } if (is_infinite() && r.is_infinite()) { return p <=> r.p; } if (is_infinite()) { return p < 0 ? partial_ordering::less : partial_ordering::greater; } if (r.is_infinite()) { return r.p < 0 ? partial_ordering::greater : 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 (!maximize) { a *= -1, b *= -1; } 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)); } } auto query(auto x) { assert(!lines.empty()); auto l = *lines.lower_bound(x); auto y = l.a * x + l.b; return maximize ? y : -y; } private: 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) { if (y == 0) { return x < 0 ? x * min_a : x * max_a; } rational r(x, y); auto z = y * (y < 0 ? min_lc.query(r) : max_lc.query(r)); return z.numerator() / z.denominator(); } T min(T x, T y) { return -max(-x, -y); } static constexpr auto inf = numeric_limits::max(); T min_a = inf, max_a = -inf; line_container min_lc; line_container max_lc; }; void solve() { int N; cin >> N; vector> P(N); line_container_2d lc; for (auto &[x, y] : P) { cin >> x >> y; lc.add(x, y); } i64 ans = 0; for (auto [x, y] : P) { ans = max({ans, lc.max(y, -x), lc.max(-y, x)}); } cout << ans << "\n"; } int main() { cin.tie(0)->sync_with_stdio(0); int t = 1; #ifdef TC cin >> t; #endif for (auto i = 0; i < t; ++i) { solve(); } }