原题链接：https://codeforces.com/contest/1388/problem/E

E. Uncle Bogdan and Projections

After returning to shore, uncle Bogdan usually visits the computer club “The Rock”, to solve tasks in a pleasant company. One day, uncle Bogdan met his good old friend who told him one unusual task…

There are nn non-intersecting horizontal segments with ends in integers points on the plane with the standard cartesian coordinate system. All segments are strictly above the OXOX axis. You can choose an arbitrary vector (a,b)(a,b), where b<0b<0 and coordinates are real numbers, and project all segments to OXOX axis along this vector. The projections shouldn’t intersect but may touch each other.

Find the minimum possible difference between xx coordinate of the right end of the rightmost projection and xx coordinate of the left end of the leftmost projection.

Input

The first line contains the single integer n(1≤n≤2000)n (1≤n≤2000) — the number of segments.

The ii-th of the next nn lines contains three integers xli,xrixl_i, xr_i and yi(−106≤xli<xri≤106;1≤yi≤106)y_i (−10^6≤xl_i<xr_i≤10^6; 1≤y_i≤10^6) — coordinates of the corresponding segment.

It’s guaranteed that the segments don’t intersect or touch.

Output

Print the minimum possible difference you can get.

Your answer will be considered correct if its absolute or relative error doesn’t exceed 10−610^{−6}.

Formally, if your answer is aa and jury’s answer is bb then your answer will be considered correct if ∣a−b∣max(1,∣b∣)≤10−6\frac{|a-b|}{max(1,|b|)}≤10^{−6}.

题目描述

在2维平面上有nn条与xx轴平行的线段，线段用xli,xrixl_i, xr_i and yi(−106≤xli<xri≤106;1≤yi≤106)y_i (−10^6≤xl_i<xr_i≤10^6; 1≤y_i≤10^6)表示，想要将线段按照某个方向投影到xx轴上，要求投影后的线段不相交，但是端点可以接触，也就是说重叠部分的长度≤0\le0，记满足上述条件按照某个方向投影后xx最大的点与xx最小的点的距离为dd，求dd的最小值。

例如：

1
2
3
4
3
1 6 2
4 6 4
4 6 6

上述输入如果按照向量(1,−1)(1,-1)的方向投影，可以得到距离为99，这就是最小值，无法得到更小的值了

解决方案

首先，要求投影后的线段不重叠，这说明任选两个线段，沿着某个方向投影，一条线段中的任意点都不能投影到另一条线段上（但是端点可能投影到端点上），如下图所示：

线段投影的方向必须处于两条绿线之外，才能够满足投影后的线段不重叠的要求，如果处于两条绿线之间，例如两条红线所示方向，则投影后的两条线段必定有重叠部分。由于投影到xx轴之后，线段本身的长度并不会发生变化，所以题目要求的最小距离必定≥\ge所有线段的长度之和，而题目要求的最小距离必定在n∗(n−1)/2n*(n-1)/2对线段的其中一个绿线方向作为投影方向取到，因为如果不是任何一个绿线方向，则说明这个方向不可能同时经过两条线段的端点，如下图所示，距离为L1+D+L2L1+D+L2

而我们可以必定可以移动投影方向，使其经过其中某两条线段的端点，使得距离减少为L1+L2L1+L2，且不会增加其他线段间的投影间距，如下图所示；与假设矛盾，因此最优的投影方向必定经过其中某两条线段的端点，例如下图中的(xr1,y1),(xl2,y2)(xr_1,y_1),(xl_2,y_2)：

假设任选一对线段，两条线段的坐标为(xl1,xr1,y1),(xl2,xr2,y2)(xl_1,xr_1,y_1),(xl_2,xr_2,y_2)，可能的投影方向为(xr1−xl2,y1−y2)(xr_1-xl_2,y_1-y_2)或者(xl1−xr2,y1−y2)(xl_1-xr_2,y_1-y_2)，假设可能取到的最小距离的某个投影方向为(a,b)(a,b)，对应的斜率为k=b/ak=b/a，则最大值为某个xri−yi∗(a/b)xr_i-y_i*(a/b)，而xri,yixr_i,y_i值是固定的，一共有nn条线段，我们可以利用凸包技巧Convex Hull Trick，以Olog(n)Olog(n)的时间复杂度求得，而可能的斜率方向的数量为O(n2)O(n^2)，需要注意的是，我们需要将可能投影到其他线段上的投影方向过滤掉，方法是，假设某对线段的22个可能的投影方向对应的斜率为(k1,k2),k1<k2(k_1,k_2),k_1<k_2，则处于(k1,k2)(k_1,k_2)之间的斜率是不符合要求的，需要过滤掉，我们遍历O(n2)O(n^2)对区间(ki1,ki2)(ki_1,ki_2)，将不符合要求的区间合并，例如(1,3)(1,3)和(2,5)(2,5)合并为一个区间(1,5)(1,5)，而(1,2)(1,2)和(2,5)(2,5)则仍保留为22个区间，不做合并，最终遍历所有区间的左右边界点（即斜率），可以分别求得对应的投影到xx轴的最大值；最小值也可以通过同样的方式得到，其中最大值和最小值之间距离最短的，即为最优解。

时间复杂度

O(n2log(n))O(n^2log(n))

代码

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
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
#include <bits/stdc++.h>
 
using namespace std;
 
template <typename T1, typename T2> istream &operator>>(istream &is, const pair<T1, T2> &pa) { is >> pa.first >> pa.second; return is; }
template <typename T> istream &operator>>(istream &is, vector<T> &vec) { for (auto &v : vec) is >> v; return is; }
template <typename T1, typename T2> ostream &operator<<(ostream &os, const pair<T1, T2> &pa) { os << "(" << pa.first << "," << pa.second << ")"; return os; }
template <typename T> ostream &operator<<(ostream &os, const vector<T> &vec) { os << "["; for (auto v : vec) os << v << ","; os << "]"; return os; }
template <typename T> ostream &operator<<(ostream &os, const deque<T> &vec) { os << "deq["; for (auto v : vec) os << v << ","; os << "]"; return os; }
template <typename T> ostream &operator<<(ostream &os, const set<T> &vec) { os << "{"; for (auto v : vec) os << v << ","; os << "}"; return os; }
template <typename T> ostream &operator<<(ostream &os, const multiset<T> &vec) { os << "{"; for (auto v : vec) os << v << ","; os << "}"; return os; }
template <typename T> ostream &operator<<(ostream &os, const unordered_set<T> &vec) { os << "{"; for (auto v : vec) os << v << ","; os << "}"; return os; }
template <typename T> ostream &operator<<(ostream &os, const unordered_multiset<T> &vec) { os << "{"; for (auto v : vec) os << v << ","; os << "}"; return os; }
template <typename TK, typename TV> ostream &operator<<(ostream &os, const unordered_map<TK, TV> &mp) { os << "{"; for (auto v : mp) os << v.first << "=>" << v.second << ","; os << "}"; return os; }
template <typename TK, typename TV> ostream &operator<<(ostream &os, const map<TK, TV> &mp) { os << "{"; for (auto v : mp) os << v.first << "=>" << v.second << ","; os << "}"; return os; }
template <typename T> void resize_array(vector<T> &vec, int len) { vec.resize(len); }
template <typename T, typename... Args> void resize_array(vector<T> &vec, int len, Args... args) { vec.resize(len); for (auto &v : vec) resize_array(v, args...); }
template <typename T1, typename T2> pair<T1, T2> operator+(const pair<T1, T2> &l, const pair<T1, T2> &r) { return make_pair(l.first + r.first, l.second + r.second); }
template <typename T1, typename T2> pair<T1, T2> operator-(const pair<T1, T2> &l, const pair<T1, T2> &r) { return make_pair(l.first - r.first, l.second - r.second); }
long long gcd(long long a, long long b) { return b ? gcd(b, a % b) : a; }
mt19937 mrand(random_device{}());
int rnd(int x) { return mrand() % x; }
 
template <unsigned int MOD>
class ModInt {
public:
    ModInt(unsigned long long _v = 0) { set_v((_v % MOD + MOD)); }
    explicit operator bool() const { return val != 0; }
    ModInt operator-() const { return ModInt() - *this; }
    ModInt operator+(const ModInt &r) const { return ModInt().set_v(val + r.val); }
    ModInt operator-(const ModInt &r) const { return ModInt().set_v(val + MOD - r.val); }
    ModInt operator*(const ModInt &r) const { return ModInt().set_v((unsigned int)((unsigned long long)(val)*r.val % MOD)); }
    ModInt operator/(const ModInt &r) const { return *this * r.inv(); }
    ModInt &operator+=(const ModInt &r) { return *this = *this + r; }
    ModInt &operator-=(const ModInt &r) { return *this = *this - r; }
    ModInt &operator*=(const ModInt &r) { return *this = *this * r; }
    ModInt &operator/=(const ModInt &r) { return *this = *this / r; }
    // ModInt &operator=(unsigned long long _v) { set_v((_v % MOD + MOD)); return *this; }
    unsigned int operator=(unsigned long long _v) { set_v((_v % MOD + MOD)); return val; }
    bool operator==(const ModInt &r) const { return val == r.val; }
    bool operator!=(const ModInt &r) const { return val != r.val; }
    ModInt pow(long long n) const {
        ModInt x = *this, r = 1;
        while (n) {
            if (n & 1)
                r *= x;
            x *= x;
            n >>= 1;
        }
        return r;
    }
    ModInt inv() const { return pow(MOD - 2); }
    unsigned int get_val() { return val; }
    friend ostream &operator<<(ostream &os, const ModInt &r) { return os << r.val; }
    friend istream &operator>>(istream &is, ModInt &r) { return is >> r.val; }
private:
    unsigned int val;
    ModInt &set_v(unsigned int _v) {
        val = (_v < MOD) ? _v : _v - MOD;
        return *this;
    }
};
constexpr unsigned int mod = 1e9+7;
using Mint = ModInt<mod>;
 
#define rep(i, a, n) for (int i = a; i < (n); i++)
#define per(i, a, n) for (int i = (n)-1; i >= a; i--)
#define pb push_back
#define mp make_pair
#define all(x) (x).begin(), (x).end()
#define fi first
#define se second
#define sz(x) ((int)(x).size())
typedef vector<int> vi;
typedef long long ll;
typedef unsigned int uint;
typedef unsigned long long ull;
typedef pair<int, int> pii;
typedef double db;
#if DEBUG
#define dbg(x) cerr << #x << " = " << (x) << " (L" << __LINE__ << ") " << __FILE__ << endl;
#else
#define dbg(x)
#endif
 
using Mint2 = ModInt<mod-1>;

template<typename T>
struct Line {
    T k, b;
    // 集合中的直线按照斜率从小到大排序，该值表示本直线与下一条直线的交点的横坐标
    mutable T intersect_x;
    bool operator<(const Line<T>& o) const { return k < o.k; }  // 用于按照斜率排序
    bool operator<(T x) const { // 用于在Query时进行二分查找
        return intersect_x < x;
    }                                                  // 用于二分查找
    T Eval(T x) const { return k * x + b; }  // 求直线在x点的y值
    T IntersectX(const Line<T>& line) const { // 求与直线line的交点的横坐标
        assert(k != line.k); // 斜率不能相等，否则除0异常
        return Div(line.b - b, k - line.k);
    }
    T Div(T a, T b) const {
        if constexpr (std::is_integral<T>::value) {
            // floored division,
            // 因为两条直线之间的交点可能是小数，但是x是整数，因此小数部分永远不会取到
            // 所以求直线交点时只需要记录<=交点横坐标值的最大整数即可
            // 3/2 -> 1; -3/2 -> -2; 4/2 -> 2; -4/2 -> 2
            return a / b - ((a ^ b) < 0 && a % b);
        } else {
            return a / b;
        }
    }
};

template <typename T, int FIND_MIN = 0>
class LineContainer {
   public:
    void Add(T k, T b) {
        if (FIND_MIN) Add(Line<T>{-k, -b, 0});
        else Add(Line<T>{k, b, 0});
    }
    // 查找使得k*x+b最大的那条直线并返回最大的k*x+b
    T Query(T x) {
        assert(!lines.empty());
        auto it = lines.begin();
        auto l = lines.lower_bound(x);
        return FIND_MIN ? -(l->Eval(x)) : l->Eval(x);
    }
   private:
    void Add(const Line<T>& line) {
        auto nxt = lines.insert(line), cur = nxt++, prev = cur;
        // 判断插入的直线后面的直线是否需要删除，如果删除则重新求相邻直线的交点
        while (Intersect(cur, nxt)) nxt = lines.erase(nxt);
        // 判断插入的直线本身是否需要删除，删除的话重新求相邻直线的交点
        if (prev != lines.begin() && Intersect(--prev, cur))
            Intersect(prev, cur = lines.erase(cur));
        // 判断插入的直线前面的那一条直线是否需要删除，删除的话重新求相邻直线的交点
        while ((cur = prev) != lines.begin() &&
               (--prev)->intersect_x >= cur->intersect_x)
            Intersect(prev, lines.erase(cur));
    }
    // 求直线l1与l2的交点横坐标（向下取整），并判断是否需要删除直线l2
    bool Intersect(typename multiset<Line<T>>::iterator l1, typename multiset<Line<T> >::iterator l2) {
        if (l2 == lines.end()) {
            l1->intersect_x = numeric_limits<T>::max();
            return false;
        }
        if (l1->k == l2->k) {
            l1->intersect_x = l1->b > l2->b ? numeric_limits<T>::max()
                                            : numeric_limits<T>::lowest();
        } else {
            l1->intersect_x = l1->IntersectX(*l2);
        }
        return l1->intersect_x >= l2->intersect_x;
    }

    multiset<Line<T>, less<>> lines;
};

class Solution {
    struct Node {
        int xl, xr, y;
        friend istream &operator>>(istream &is, Node &r) { return is >> r.xl >> r.xr >> r.y; }
    };
public:
    void Solve() {
        int n;
        while(cin>>n) {
            vector<Node> segments(n);
            cin>>segments;

            vector<pair<double, double>> slopes;
            rep(i,0,n) {
                rep(j,0,n) {
                    if (segments[j].y <= segments[i].y) continue;

                    double s1 = double(segments[j].xl - segments[i].xr) / (segments[j].y - segments[i].y);
                    double s2 = double(segments[j].xr - segments[i].xl) / (segments[j].y - segments[i].y);
                    slopes.emplace_back(mp(s1, s2));
                }
            }

            sort(all(slopes));
            dbg(slopes);

            int cur = 0;
            rep(i,1,sz(slopes)) {
                if (slopes[i].fi < slopes[cur].se) {
                    slopes[cur].se = max(slopes[cur].se, slopes[i].se);
                } else {
                    cur++;
                    slopes[cur] = slopes[i];
                }
            }
            slopes.resize(cur+1);
            dbg(slopes);

            LineContainer<double, 0> lines1;
            rep(i,0,sz(segments)) {
                lines1.Add(-segments[i].y, segments[i].xr);
            }
            
            LineContainer<double, 1> lines2;
            rep(i,0,sz(segments)) {
                lines2.Add(-segments[i].y, segments[i].xl);
            }
            
            double ans = numeric_limits<double>::max();
            rep(i,0,sz(slopes)) {
                ans = min(ans, lines1.Query(slopes[i].fi) - lines2.Query(slopes[i].fi));
                ans = min(ans, lines1.Query(slopes[i].se) - lines2.Query(slopes[i].se));
            }

            cout << fixed << setprecision(9) << ans << endl;
        }
    }
private:
};
 
// #define USACO 1
void set_io(const string &name = "") {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
#if FILE_IO || USACO
    if (!name.empty()) {
        freopen((name + ".in").c_str(), "r", stdin);
        freopen((name + ".out").c_str(), "w", stdout);
    }
#endif
}

int main() {
#if USACO
    set_io("time");
#else
    set_io("tmp");
#endif
    Solution().Solve();

    return 0;
}