题意：给n( n ≤ n\leq n≤ 2000)条水平线段，求一个方向向量，使得这些直线按照该方向向量向x轴做投影后，所有线段不相交，求这些线段所覆盖的位置的最左端的和最右端的距离最小。 思路： 考虑两条线段AB、CD，只有AC、BD才可能成为答案。同时，斜率处于AC与BD之间的向量不能作为答案，否则会使AB、CD的投影相交。 所以，我们需要枚举出所有可能的答案，然后用区间覆盖的方式除去矛盾的线段，然后再比较哪一个向量求得的答案最小的答案。 对于一个已知向量，我们需要求出投影后最左端和最右端的点。可以建凸包，然后根据叉积（或者斜率）进行二分即可。 注意，可能所有直线都在同一高度，此时需要特判垂直的情况（见样例3）。
#include<iostream> #include<cstdio> #include<cstdlib> #include<cstring> #include<algorithm> #include<cmath> using namespace std; typedef long double LD; typedef long long LL; const LD inf = 1e18; const int N = 2010; struct LINE{ LL xl, xr, y; bool operator < (const LINE & other) const{ return y < other.y;} }line[N]; struct POINT{ LL x, y; POINT(LL a = 0, LL b = 0) {x = a; y = b;} POINT operator - (const POINT & b){return POINT (x - b.x, y - b.y);} }pt[N * 2]; LL X(POINT a, POINT b) { return a.x * b.y - a.y * b.x;} struct QU{ LL x, y, xx, yy; int opt; QU(LL a = 0, LL b = 0, LL c = 0, LL d = 0, int e = 0) {x = a; y = b; xx = c; yy = d; opt = e;} bool operator < (const QU & b) const{ return X(POINT(xx - x, yy - y), POINT(b.xx - b.x, b.yy - b.y)) > 0 || X(POINT(xx - x, yy - y), POINT(b.xx - b.x, b.yy - b.y)) == 0 && opt < b.opt;} }qu[N * N]; int que[N * 2], vist[N * N]; int top, tot, mid_top; LL dist(POINT x, POINT y) { return (x.x - y.x) * (x.x - y.x) + (x.y - y.y) * (x.y - y.y); } int cmp(POINT x, POINT y) { return X(x - pt[1], y - pt[1]) > 0 || (X(x - pt[1], y - pt[1]) == 0 && dist(x, pt[1]) < dist(y, pt[1])); } void get_convex() { int k = 1; for(int i = 1; i <= tot; i++) if(pt[i].y < pt[k].y || (pt[i].y == pt[k].y && pt[i].x < pt[k].x)) k = i; swap(pt[k], pt[1]); sort(pt + 2, pt + tot + 1, cmp); que[1] = 1; top = 1; for(int i = 2; i <= tot; i++) { while(top > 1 && X(pt[que[top]] - pt[que[top - 1]], pt[i] - pt[que[top - 1]]) <= 0) top--; que[++top] = i; } que[top + 1] = 1; mid_top = 1; for(; mid_top <= top; mid_top++) if(pt[que[mid_top]].y > pt[que[mid_top + 1]].y) break; } LD get_l(int id) { int l = mid_top; int r = top + 1; while(r - l > 1) { int mid = (l + r) >> 1; if(X(pt[que[mid + 1]] - pt[que[mid]], POINT(qu[id].x - qu[id].xx, qu[id].y - qu[id].yy)) >= 0) l = mid; else r = mid; } return min((LD)pt[que[l]].x - (LD)((qu[id].xx - qu[id].x) * pt[que[l]].y) / (LD) (qu[id].yy - qu[id].y),(LD)pt[que[r]].x - (LD)((qu[id].xx - qu[id].x) * pt[que[r]].y) / (LD) (qu[id].yy - qu[id].y)); } LD get_r(int id) { int l = 1; int r = mid_top + 1; while(r - l > 1) { int mid = (l + r) >> 1; if(X(pt[que[mid + 1]] - pt[que[mid]], POINT(qu[id].xx - qu[id].x, qu[id].yy - qu[id].y)) >= 0) l = mid; else r = mid; } return max((LD)pt[que[l]].x - (LD)((qu[id].xx - qu[id].x) * pt[que[l]].y) / (LD) (qu[id].yy - qu[id].y),(LD)pt[que[r]].x - (LD)((qu[id].xx - qu[id].x) * pt[que[r]].y) / (LD) (qu[id].yy - qu[id].y)); } int cmp1(LINE x, LINE y) { return x.xl < y.xl;} LD solve_RT(int n) { sort(line + 1, line + n + 1, cmp1); LL now = line[1].xr; for(int i = 2; i <= n; i++) { if(line[i].xl < now) return inf; now = line[i].xr; } return (LD)(now - line[1].xl); } int main() { int n; scanf("%d", &n); for(int i = 1; i <= n; i++) { scanf("%lld%lld%lld", &line[i].xl, &line[i].xr, &line[i].y); pt[++tot] = POINT(line[i].xl, line[i].y); pt[++tot] = POINT(line[i].xr, line[i].y); } LD ans = inf; ans = solve_RT(n); sort(line + 1, line + n + 1); int cnt = 0; for(int i = 1; i <= n; i++) for(int j = i + 1; j <= n; j++) { if(line[i].y == line[j].y) continue; qu[++cnt] = QU(line[i].xl, line[i].y, line[j].xr, line[j].y, 1); qu[++cnt] = QU(line[i].xr, line[i].y, line[j].xl, line[j].y, -1); } sort(qu + 1, qu + cnt + 1); int now = 0; for(int i = 1; i <= cnt; i++) { if(qu[i].opt == 1) { if(now > 0) vist[i] = 1; now++; } else { now--; if(now > 0) vist[i] = 1; } get_convex(); for(int i = 1; i <= cnt; i++) if(!vist[i]) { LD l = get_l(i); LD r = get_r(i); ans = min(ans, r - l); } printf("%.9Lf",ans); return 0; }