https://ac.nowcoder.com/acm/contest/890/G
题意
平面上有偶数个点，现在你要找出一条直线将这些点隔开成数量相同的两部分，直线不能穿过任何一点
问离直线最近的点离直线的距离最大是多少？
题解
必须知道一个结论：
这条最优的直线一定是与某两点连线平行或垂直。
那么我们可以枚举直线斜率n^2，然后求出所有点到这条直线的距离并排序nlogn，
那么中间的两个的差值除以2就是答案。
总时间复杂度n^3logn，n最大为300可以接受。
举个例子，如图（其实就是第一个样例），我们要把A,B,C,D,E,F分开，假设我们已经枚举到平行BD的直线AG，
那么答案为（BM-CH）/2。
代码很好写
1 #define bug(x) cout<<#x<<" is "<<x<<endl 2 #define IO std::ios::sync_with_stdio(0) 3 #include <bits/stdc++.h> 4 #define iter ::iterator 5 #define pa pair<int,ll> 6 using namespace std; 7 #define ll long long 8 #define mk make_pair 9 #define pb push_back 10 #define se second 11 #define fi first 12 ll mod=998244353; 13 const int N=1e5+5; 14 int n; 15 struct node{ 16 double x,y; 17 }p[N]; 18 double ans=0; 19 double d[N]; 20 void cal(double k){ 21 for(int i=1;i<=n;i++){ 22 d[i]=(k*p[i].x-p[i].y)/sqrt(1+k*k); 23 } 24 sort(d+1,d+1+n); 25 double res=(d[n/2+1]-d[n/2])/2; 26 ans=max(ans,res); 27 } 28 int main(){ 29 scanf("%d",&n); 30 for(int i=1;i<=n;i++){ 31 scanf("%lf%lf",&p[i].x,&p[i].y); 32 } 33 for(int i=1;i<=n;i++){ 34 for(int j=1;j<i;j++){ 35 double k=(p[i].y-p[j].y)/(p[i].x-p[j].x); 36 cal(k); 37 k=-1/k; 38 cal(k); 39 } 40 } 41 printf("%.10lf ",ans); 42 }