HDU多校第十场 1007 Closest Pair of Segments —— 计算几何

题目链接：点我啊╭(╯^╰)╮

题目大意：

    求 $n$ 条线段的最近线段的距离

解题思路：

    暴力枚举每两条线段的距离
    但要对每条线段的左端点排序
    若左侧线段的右端点 $x$ 与右侧线段的左端点 $x$ 差值大于了 $ans$
    则直接 $break$，这样竟然能优化 $19$ 秒

核心：最近线段距离优化

#include<bits/stdc++.h>
#define deb(x) cerr<<#x<<" = "<<(x)<<'\n';
using namespace std;
typedef long long ll;
const double eps = 1e-6;
struct point {double x, y;point() {}point(double X, double Y) {x = X, y = Y;}point operator - (const point &A) {return point(x-A.x, y-A.y);}bool operator < (const point &A)const {if(x == A.x) return y < A.y;return x < A.x;}
} ;inline int dcmp(double x) {if(fabs(x) < eps) return 0;return x < 0 ? -1 : 1;
}
inline double cross(point A, point B) {	//	叉积return A.x*B.y - B.x*A.y;
}
inline double dot(point A, point B) {	//	点积return A.x*B.x + B.y*A.y;
}double getdis(point a, point b) {	//	两点距离return sqrt((a.x-b.x)*(a.x-b.x) + (a.y-b.y)*(a.y-b.y));
}struct Line {point s, e;Line() {}Line(point S, point E) {s = S, e = E;}double length() {return getdis(s, e);}
};//点到直线距离
inline double point_to_line(point p, Line a) {return fabs(cross(p-a.s, a.e-a.s) / a.length());
}//点到线段距离
inline double point_to_seg(point p, Line a) {if(dcmp(dot(p-a.s, a.e-a.s))<0 || dcmp(dot(p-a.e, a.s-a.e))<0)return min(getdis(p, a.e), getdis(p, a.s));return point_to_line(p, a);
}//线段到线段的距离
inline double seg_to_seg(Line u, Line v) {return min( min(point_to_seg(u.s, v), point_to_seg(u.e, v)),\min( point_to_seg(v.s, u), point_to_seg(v.e, u)) );
}bool cmp(const Line &u, const Line &v) {return u.s < v.s;
}const int maxn = 1e4 + 5;
int T, n;
Line line[maxn];
int main() {scanf("%d", &T);while(T--) {scanf("%d", &n);for(int i=1; i<=n; i++) {scanf("%lf%lf", &line[i].s.x, &line[i].s.y);scanf("%lf%lf", &line[i].e.x, &line[i].e.y);if(line[i].e < line[i].s) swap(line[i].s, line[i].e);}sort(line+1, line+1+n, cmp);double ans = 1e10;for(int i=1; i<=n; i++) {for(int j=i+1; j<=n; j++) {if(dcmp(line[j].s.x-line[i].e.x - ans) > 0) break;ans = min(ans, seg_to_seg(line[i], line[j]));}}printf("%.9f\n", ans);}
}