凸包最大内切圆

定义： 给一个凸包，求这个凸包里能放的最大圆(一般要求半径)。

凸多边形的范围等价于各个边的半平面交，可以发现，当凸包各个边向内收缩r时，内切圆的半径就会减少r。当缩到半平面交恰好不存在时，收缩的r就是内切圆的最大半径了。

可以二分找收缩的r值，若收缩后半平面交不为空集，则可以存在此半径的圆。

题目：POJ - 3525

#include<bits/stdc++.h>
#define ll long long
#define lf double
#define IOS std::ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define Rep(i,l,r) for(int i=(l);i<=(r);i++)
using namespace std;

struct Point{
    double x,y;
};
typedef Point vector_t;
typedef Point point_t;
struct Line
{
    Point x;
    vector_t v;
};

Point operator-(const Point&a,const Point&b){
    Point c;
    c.x=a.x-b.x;
    c.y=a.y-b.y;
    return c; 
}

double Cross(const vector_t& x, const vector_t& y)
{
	return x.x * y.y - x.y * y.x;
}

double eps=1e-6;
int dcmp(double x)
{
    if(fabs(x)<eps)return 0;
    if(x>0)return 1;
    return -1;
}

int n;
Point p[500];
vector<vector_t>v;
vector<vector_t>normal;
Point tmpP[500];
Line tmpL[500];

vector_t operator*(const vector_t& v,double t){
    vector_t z=v;
    z.x*=t;z.y*=t;
    return z;
}
vector_t operator+(const vector_t& a,const vector_t&b){
    vector_t z;
    z.x=a.x+b.x;
    z.y=a.y+b.y;
    return z;
}
point_t GetLineIntersection(Line a,Line b){//求两直线交点
    Point P=a.x;vector_t v=a.v;
    Point Q=b.x;vector_t w=b.v;
    vector_t u = P-Q;
    double t = Cross(w, u)/Cross(v, w);
    return P+v*t;//由直线的点向式而来
}

double Dot(vector_t A, vector_t B){
    return A.x*B.x + A.y*B.y;
}
double Length(vector_t A){
    return sqrt(Dot(A, A));
}
vector_t Normal(vector_t A){//向量A左转90°的单位法向量
    double L = Length(A);
    vector_t z;
    z.x=-A.y/L;
    z.y=A.x/L;
    return z;
}

bool cmp1(const Line& a,const Line& b)
{
    return atan2(a.v.y,a.v.x)<atan2(b.v.y,b.v.x);
}
bool cmp2(const Line& a,const Line& b)
{
	double f=Cross(a.v,b.v);
	if(f==0) return 0;
	else if(f>0) return 0;
	return 1;
}
bool Onleft(Line l,Point p) {return Cross(l.v,(p-l.x)) > 0;}//ToLeftTest
int HalfPol(Line *l,int n,vector<Point> &p)
{
    sort(l,l+n,cmp1);//极角排序,cmp1/cmp2都可以
    int hd = 0,tl = 0;
    tmpL[0] = l[0];
    for(int i=0;i<n;i++)
    {
        while(hd<tl&&!Onleft(l[i],tmpP[tl-1]))tl--;
        while(hd<tl&&!Onleft(l[i],tmpP[hd]))hd++;
        tmpL[++tl] = l[i];
        if(!dcmp(Cross(tmpL[tl].v,tmpL[tl-1].v)))
        {
            tl--;
            if(Onleft(tmpL[tl],l[i].x))tmpL[tl]=l[i];
        }
        if(hd<tl)tmpP[tl-1] = GetLineIntersection(tmpL[tl-1],tmpL[tl]);
    }
    while(hd<tl&&!Onleft(tmpL[hd],tmpP[tl-1]))tl--;
    if(tl-hd<=1)return 0;
    tmpP[tl] = GetLineIntersection(tmpL[hd],tmpL[tl]);
    for(int i=hd;i<=tl;i++)p.push_back(tmpP[i]);
    return tl-hd+1;
}

int main()
{
    while(cin>>n)
    {
        if(!n)break;
        v.clear();normal.clear();
        Rep(i,0,n-1){
            double x,y;
            cin>>x>>y;
            p[i].x=x;p[i].y=y;
        }
        for(int i=0;i<n;i++){
            v.push_back(p[(i+1)%n]-p[i]);
            normal.push_back(Normal(v[i]));
        }

        double l=0,r=20000;
        while(r-l>eps)
        {
            double mid=(l+r)/2;
            Line L[500];
            for(int i=0;i<n;i++){
                L[i]=((Line){p[i]+normal[i]*mid,v[i]});
                //直线向法向量方向移动mid距离,就是收缩
            }
            vector<Point>p2;
            HalfPol(L,n,p2);
            if(p2.empty()){r=mid;}
            else l=mid;
        }
        printf("%.6f\n",l);
    }
    return 0;
}

计算几何各种玄学，最后的结果如果用 %.6lf 就会WA。

参考：半平面交+二分求最大内切圆