1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74

#include <bits/stdc++.h>
#ifdef local
#define debug(args...) qqbx(#args, args)
template <typename ...T> void qqbx(const char *s, T ...args) {
    int cnt = sizeof...(T);
    ((std::cerr << "(" << s << ") = (") , ... , (std::cerr << args << (--cnt ? ", " : ")\n")));
}
#else
#define debug(...) ((void)0)
#endif
#define pb emplace_back
#define all(v) begin(v),end(v)

using namespace std;
using ll = long long;
using ld = double;
using pii = pair<int,int>;
const int N = 1025;
const ll INF = 1e18;

ll ori(pii a, pii b, pii c) {
    return 1LL * (a.second - b.second) * (c.first - a.first)
            - 1LL * (a.second - c.second) * (b.first - a.first);
}
ld calc(pii L, ld x) {
    return L.first * x + L.second;
}
ld intersect(pii a, pii b) {
    return  (a.second - b.second) / ld(b.first - a.first);
}
signed main() {
    ios_base::sync_with_stdio(0), cin.tie(0);
    int n;
    cin >> n;
    vector<pair<int,int>> car(n);
    for(auto &[v, s]: car) cin >> v >> s;
    sort(all(car));
    vector<pair<int,int>> lo, up;
    for(auto [a, b]: car) {
        while(up.size() >= 2 && ori(up[up.size()-2], up.back(), {a, b}) >= 0)
            up.pop_back();
        up.pb(a, b);
    }
    reverse(all(car));
    for(auto [a, b]: car) {
        while(lo.size() >= 2 && ori(lo[lo.size()-2], lo.back(), {a, b}) >= 0)
            lo.pop_back();
        lo.pb(a, b);
    }
    /* reverse(all(up)); */
    /* cerr << "lo =\n"; */
    /* for(auto [a, b]: lo) debug(a, b); */
    /* cerr << "up =\n"; */
    /* for(auto [a, b]: up) debug(a, b); */
    int mx = -1e9, mn = 1e9;
    for(auto &[v, s]: car) mx = max(mx, s), mn = min(mn, s);
    ld ans = mx - mn;
    size_t i = 0, j = 0;
    debug(lo.size(), up.size());
    while(i+1 < lo.size() || j+1 < up.size()) {
        ld xi = i+1 < lo.size() ? intersect(lo[i], lo[i+1]) : 1e18;
        ld xj = j+1 < up.size() ? intersect(up[j], up[j+1]) : 1e18;
        debug(xi, xj);
        debug(i, j);
        if(xi < xj) {
            if(xi >= 0) ans = min(ans, calc(up[j], xi) - calc(lo[i], xi));
            i++;
        } else {
            if(xj >= 0) ans = min(ans, calc(up[j], xj) - calc(lo[i], xj));
            j++;
        }
    }
    printf("%.2lf\n", ans);
}