uva1396 Most Distant Point from the Sea

二分答案，验证答案$x$的时候把所有边向内移动$x$的距离求半平面交，如果有解就说明可行。

#include<cstdio>
#include<algorithm>
#include<cmath>
using namespace std;
const double eps=1e-8;
const int maxn=110;
int cmp(double x)
{if (x>=eps) return 1;if (fabs(x)<eps) return 0;return -1;
}
struct Vector
{double x,y;Vector operator + (const Vector &v) const{return (Vector){x+v.x,y+v.y};}Vector operator - (const Vector &v) const{return (Vector){x-v.x,y-v.y};}Vector operator * (const double &k) const{return (Vector){x*k,y*k};}Vector operator / (const double &k) const{return (Vector){x/k,y/k};}double ang() const{return atan2(y,x);}
}a[maxn],f[maxn];
typedef Vector Point;
double dot(Vector v,Vector u)
{return v.x*u.x+v.y*u.y;
}
double cross(Vector v,Vector u)
{return v.x*u.y-v.y*u.x;
}
double len(Vector v)
{return sqrt(dot(v,v));
}
Vector normal(Vector v)
{Vector u=(Vector){-v.y,v.x};return u/len(u);
}
struct Line
{Point p;Vector v;bool operator < (const Line &l) const{return cmp(v.ang()-l.v.ang())==-1;}
}g[maxn],que[maxn];
bool onleft(Point p,Line l)
{return cmp(cross(p-l.p,l.v))==-1;
}
Point intersection(Line l,Line m)
{double t=cross(m.v,l.p-m.p)/cross(l.v,m.v);return l.p+l.v*t;
}
int n;
int check(double x)
{int hd=1,tl=1;Vector v;for (int i=1;i<=n;i++){v=a[i+1]-a[i];g[i]=(Line){a[i]+normal(v)*x,v};}sort(g+1,g+n+1);que[1]=g[1];for (int i=2;i<=n;i++){while (hd<tl&&!onleft(f[tl-1],g[i])) tl--;while (hd<tl&&!onleft(f[hd],g[i])) hd++;if (!(que[tl]<g[i])&&!(g[i]<que[tl])){if (!onleft(f[tl-1],g[i])) que[tl]=g[i];}else que[++tl]=g[i];if (hd<=tl) f[tl-1]=intersection(que[tl-1],que[tl]);}while (hd<tl&&!onleft(f[tl-1],que[hd])) tl--;return tl-hd>=2;
}
void solve()
{double l,r,mid;for (int i=1;i<=n;i++) scanf("%lf%lf",&a[i].x,&a[i].y);a[n+1]=a[1];l=0,r=5e4;while (fabs(r-l)>1e-6){mid=(l+r)/2;if (check(mid)) l=mid;else r=mid;}printf("%f\n",l);
}
int main()
{//freopen("a.in","r",stdin);while (scanf("%d",&n)&&n) solve();
}