#include #include using namespace std; #define rep(i, n) for (long long i = 0; i < (long long)(n); i++) #define FOR(i, s, e) for (long long i = (long long)(s); i <= (long long)(e); i++) #define printYesNo(is_ok) puts(is_ok ? "Yes" : "No"); #define SORT(v) sort(v.begin(), v.end()); #define RSORT(v) sort(v.rbegin(), v.rend()); #define REVERSE(v) reverse(v.begin(), v.end()); long long op(long long a, long long b) { return a + b; } long long e() { return 0; } template pair fibonacci_search(long long x_low, long long x_high, function f) { assert(x_low < x_high); long long offset = x_low - 1; T INF = minimize ? numeric_limits::max() : numeric_limits::lowest(); auto comp = [](T a, T b) -> bool { return minimize ? a >= b : a <= b; }; vector fib = {1, 1}; while (fib.back() <= x_high - offset) { fib.push_back(fib[fib.size() - 1] + fib[fib.size() - 2]); } unordered_map fx_cache; auto eval = [&](long long idx) -> T { long long x = idx + offset; if (x_low <= x && x <= x_high) { if (!fx_cache.contains(x)) { fx_cache[x] = f(x); } return fx_cache[x]; } return INF; }; long long l_idx = 0, r_idx = fib.back(); while (2 <= fib.size()) { long long step_len = fib[fib.size() - 2]; long long mid_l_idx = r_idx - step_len, mid_r_idx = l_idx + step_len; T fl = eval(mid_l_idx), fr = eval(mid_r_idx); if (comp(fl, fr)) { l_idx = mid_l_idx; } else { r_idx = mid_r_idx; } fib.pop_back(); } return {l_idx + offset, eval(l_idx)}; } int main() { int N; cin >> N; vector> ab(N); rep(i, N) { cin >> ab[i].first >> ab[i].second; } auto f = [&](long long x) -> long long { long long mx = 0, mn = INT32_MAX; for (auto [a, b] : ab) { mx = max(mx, a + b * x); mn = min(mn, a + b * x); } return mx - mn; }; if (count(ab.begin(), ab.end(), pair{0, 0}) == N) { cout << 1 << endl; } else { auto [x, fx] = fibonacci_search(1, 1000000000, f); cout << x << endl; } return 0; };