C++11(clang++ 3.9) 解法, 执行用时: 99ms, 内存消耗: 26744K, 提交时间: 2018-05-27 14:18:27

#include<bits/stdc++.h>
using namespace std;
const int maxn=20000;
const double eps=1e-8;
struct Point
{
    double x,y;
    Point(double x=0,double y=0):x(x),y(y) {}
};
typedef Point Vector;
struct DLine
{
    Point P;
    Vector v;
    double ang;
    DLine() {}
    DLine(Point P,Vector v):P(P),v(v)
    {
        ang=atan2(v.y,v.x);
    }
    bool operator < (const DLine& L) const
    {
        return ang<L.ang;
    }
};
Vector operator + (Vector A,Vector B)
{
    return Vector(A.x+B.x,A.y+B.y);
}
Vector operator - (Vector A,Vector B)
{
    return Vector(A.x-B.x,A.y-B.y);
}
Vector operator * (Vector A,double p)
{
    return Vector(A.x*p,A.y*p);
}
int dcmp(double x)
{
    if(fabs(x)<eps) return 0;
    else return x<0?-1:1;
}
bool operator == (const Point& a,const Point& b)
{
    return dcmp(a.x-b.x)==0 && dcmp(a.y-b.y)==0;
}
double Dot(Vector A,Vector B)
{
    return A.x*B.x+A.y*B.y;
}
double Length(Vector A)
{
    return sqrt(Dot(A,A));
}
double Cross(Vector A,Vector B)
{
    return A.x*B.y-A.y*B.x;
}
Vector Normal(Vector A)//向量的单位法线，即左转90度
{
    double L=Length(A);
    return Vector(-A.y/L,A.x/L);
}
bool OnLeft(DLine L,Point p)
{
    return Cross(L.v,p-L.P)>0;
}
Point GetIntersection(DLine a,DLine b)
{
    Vector u=a.P-b.P;
    double t=Cross(b.v,u)/Cross(a.v,b.v);
    return a.P+a.v*t;
}
int HalfPlaneIntersection(DLine* L,int n){
    sort(L,L+n);
    int first,last;
    Point *p=new Point[n];
    DLine *q=new DLine[n];
    q[first=last=0]=L[0];
    for(int i=1; i<n; i++)
    {
        while(first<last && !OnLeft(L[i],p[last-1])) last--;
        while(first<last && !OnLeft(L[i],p[first])) first++;
        q[++last]=L[i];
        if(fabs(Cross(q[last].v,q[last-1].v))<eps)
        {
            last--;
            if(OnLeft(q[last],L[i].P)) q[last]=L[i];
        }
        if(first<last) p[last-1]=GetIntersection(q[last-1],q[last]);
    }
    while(first<last && !OnLeft(q[first],p[last-1])) last--;
    if(last-first <= 1) return 0;
    p[last]=GetIntersection(q[last],q[first]);
    return (last-first+1);
}
int n;
Point p[maxn];
DLine l[maxn];
Vector v[maxn],v2[maxn];
void solve()
{
    double left=0,right=10000;//二分
    while(right-left>1e-6)
    {
        double mid=left+(right-left)/2;
        for(int i=0; i<n; i++)
            l[i]=DLine(p[i]+v2[i]*mid,v[i]);
        int m=HalfPlaneIntersection(l,n);
        if(!m) right=mid;
        else left=mid;
    }
    cout<<fixed<<setprecision(10)<<left<<endl;
    //printf("%.6lf\n",left);
}

int main()
{
   // freopen("in.cpp","r",stdin);
    while((cin>>n) && n)
    {
        for(int i=0; i<n; i++)
            //scanf("%lf%lf",&p[i].x,&p[i].y);
            cin>>p[i].x>>p[i].y;
        for(int i=0; i<n; i++)
        {
            v[i]=p[(i+1)%n]-p[i];
            v2[i]=Normal(v[i]);
        }
        solve();
    }
    return 0;
}

C++14(g++5.4) 解法, 执行用时: 207ms, 内存消耗: 23904K, 提交时间: 2018-05-27 13:32:21

#include<cstdio>
#include<cmath>
#include<algorithm>
#define MAXN 150000
using namespace std;
struct poi
{
    double x,y;
    poi(double x = 0,double y = 0) :x(x),y(y) {}
}pos[MAXN],a[MAXN],out[MAXN],v1[MAXN],v2[MAXN];
typedef poi vec;
vec operator +(vec A,vec B) {return vec(A.x+B.x, A.y+B.y);}
vec operator -(vec A,vec B) {return vec(A.x-B.x, A.y-B.y);}
vec operator *(vec A,double p) {return vec(A.x*p, A.y*p);}
const double eps = 1e-7;
int dcmp(double x)
{
    if(fabs(x) < eps) return 0;
    else return x>0?1:-1;
}
bool operator <(vec A, vec B)
{
    if(A.x == B.x) return A.y < B.y;
    else return A.x < B.x;
}
double cross(vec A,vec B) {return A.x*B.y - A.y*B.x;}
double dot(vec A,vec B) {return A.x*B.x + A.y*B.y;}
double length(vec A) {return sqrt(dot(A,A));}
vec normal(vec A) {double L = length(A); return vec(-A.y/L, A.x/L);}
struct Line
{
    poi p; vec v;
    double ang;
    Line(){}
    Line(poi p,vec v) :p(p),v(v) {ang = atan2(v.y,v.x);} 
    bool operator <(const Line &b)const{return ang < b.ang;}
}L[MAXN],Q[MAXN];
bool Onleft(Line A,poi p) {return cross(A.v, p-A.p) > 0;}
poi GetLineIntersection(Line A,Line B)
{
    double t = cross(B.v, A.p-B.p) /cross(A.v, B.v);
    return A.p + A.v*t;
}
int HalfplaneIntersection(int n)
{
    sort(L,L+n);
    int head = 0,tail = 0;
    Q[0] = L[0];
    for(int i = 0; i < n; i++)
    {
        while(head < tail&& !Onleft(L[i], a[tail-1])) --tail;
        while(head < tail&& !Onleft(L[i], a[head])) ++head;
        Q[++tail] = L[i];
        if(fabs(cross(Q[tail].v,Q[tail-1].v)) < eps){
            tail--;
            if(Onleft(Q[tail], L[i].p)) Q[tail] = L[i];
        }
        if(head < tail) a[tail-1] = GetLineIntersection(Q[tail], Q[tail-1]);
    }
    while(head < tail&& !Onleft(Q[head], a[tail-1])) --tail;
    if(tail - head <= 1) return 0;
    a[tail] = GetLineIntersection(Q[head], Q[tail]);

    int m = 0;
    for(int i = head; i <= tail; i++) out[m++] = a[i];
    return m;
}
int main()
{
    int n;
    while(scanf("%d",&n) != EOF&&n)
    {
        for(int i = 0; i < n; i++) scanf("%lf%lf",&pos[i].x,&pos[i].y);
        for(int i = 0; i < n; i++)
        {
            v1[i] = pos[(i+1)%n] - pos[i];
            v2[i] = normal(v1[i]);
        }
        double l = 0, r = 1e10, mid;
        for(int i=0;i<100;i++)
        {
            mid = (l+r)/2;
            for(int i = 0; i < n; i++) L[i] = Line(pos[i] + v2[i]*mid, v1[i]);
            int m = HalfplaneIntersection(n);
            if(!m) r = mid; else l = mid;
        }
        printf("%.15f\n",l);
    }
}