一看就是有意思的题目； 然后去考fop_zz； 他说他做过了；
https://www.luogu.org/problem/show?pid=1663 我们怎么搞呢； 显然就是求很多半平面的交； 我们考虑二分这个答案； 那么怎么去验证呢？ 我们对于每一条直线解析式 y=ax+b 如果a<0,那么x的显然要在这条线的右边； 如果a>0，那么x要在其左边； 如果a==0，那么y就要在这条线的上面； 所以我们通过这3个条件去做就好了； 对于二分的每一个y; 找到x可取范围左边x1; 右边x2; 如果x2>=x1就是可以的；
#include<bits/stdc++.h> using namespace std; const int N=5e3+5; int x[N],y[N]; double a1[N],b1[N],a2[N],b2[N],l,r,mid; int n,m,t1,t2; void make(double x1,double y1,double x2,double y2){ if(fabs(y1-y2)<1e-8){l=max(l,y1);return;} double A=(y1-y2)/(x1-x2); double B=y1-A*x1; if(A<0){t1++;a1[t1]=A;b1[t1]=B;} else {t2++;a2[t2]=A;b2[t2]=B;} } bool check(double y){ double x1=0,x2=x[n],X; for(int i=1;i<=t1;i++)x1=max(x1,(y-b1[i])/a1[i]); for(int i=1;i<=t2;i++)x2=min(x2,(y-b2[i])/a2[i]); return (x2>x1)||(fabs(x2-x1)<1e-8); } int main() { scanf("%d",&n); for(int i=1;i<=n;i++)scanf("%d%d",&x[i],&y[i]); for(int i=1;i<n;i++)make(x[i],y[i],x[i+1],y[i+1]); r=1e6; while((r-l)>1e-4){ mid=(l+r)/2.; if(check(mid))r=mid;else l=mid; } printf("%.2lf",mid); }