<题目链接>
题目大意：
给出一个四面环海的凸多边形岛屿，求出这个岛屿中的点到海的最远距离。
解题分析：
仔细思考就会发现，其实题目其实就是让我们求该凸多边形内内切圆的最大半径是多少。但是，这个最大半径，没有什么比较好的求法，于是，我们可以想到二分答案求半径。对于二分的半径，我们可以将该凸多边形的边界向内平移 r 的距离，然后再用半平面交法，用这些平移后的直线去切割原凸多边形，如果最终切得的区域不为空，则二分枚举更大的半径，反之减小枚举的半径。知道恰好围成的区域为空（或恰好不为空）为止。
#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
using namespace std; const double eps = 1e-;
const double inf = 1e9;
const int MAXN = ;
int m;//保存多边形的点数
double r;//保存内移距离
int cCnt, curCnt;//此时cCnt为最终切割得到的多边形的顶点数、暂存顶点个数 struct point
{
double x, y;
};
point points[MAXN], p[MAXN], q[MAXN];//读入的多边形的顶点（顺时针）、p为存放最终切割得到的多边形顶点的数组、暂存核的顶点 void getline(point x, point y, double &a, double &b, double &c) //两点x、y确定一条直线a、b、c为其系数
{
a = y.y - x.y;
b = x.x - y.x;
c = y.x * x.y - x.x * y.y;
} void initial()
{
for (int i = ; i <= m; ++i)p[i] = points[i];
p[m + ] = p[];
p[] = p[m];
cCnt = m;
} point intersect(point x, point y, double a, double b, double c) //定比分点法，求两条直线的交点
{
double u = fabs(a * x.x + b * x.y + c);
double v = fabs(a * y.x + b * y.y + c);
point pt;
pt.x = (x.x * v + y.x * u) / (u + v);
pt.y = (x.y * v + y.y * u) / (u + v);
return pt;
} void cut(double a, double b, double c) //利用半平面交求出切割后多边形的所有顶点
{
curCnt = ;
for (int i = ; i <= cCnt; ++i)
{
if (a*p[i].x + b * p[i].y + c >= )q[++curCnt] = p[i]; // c因为精度问题，可能会偏小。所以有些点本应在右側而没在。
else
{
if (a*p[i - ].x + b * p[i - ].y + c > )
{
q[++curCnt] = intersect(p[i], p[i - ], a, b, c);
}
if (a*p[i + ].x + b * p[i + ].y + c > )
{
q[++curCnt] = intersect(p[i], p[i + ], a, b, c);
}
}
} for (int i = ; i <= curCnt; ++i)p[i] = q[i];
p[curCnt + ] = q[];
p[] = p[curCnt];
cCnt = curCnt;
} int dcmp(double x) //控制精度
{
if (fabs(x)<eps) return ;
else return x< ? - : ;
} void solve()
{
initial(); //初始化存放多边形顶点的p数组 for (int i = ; i <= m; ++i) { point ta, tb, tt; //得到平移后的直线
tt.x = points[i + ].y - points[i].y;
tt.y = points[i].x - points[i + ].x;
double k = r / sqrt(tt.x * tt.x + tt.y * tt.y);
tt.x = tt.x * k;
tt.y = tt.y * k;
ta.x = points[i].x + tt.x;
ta.y = points[i].y + tt.y;
tb.x = points[i + ].x + tt.x;
tb.y = points[i + ].y + tt.y; double a, b, c; //接下来用这些平移后的直线去切割原多边形
getline(ta, tb, a, b, c);
cut(a, b, c);
}
} void Reverse() { //规整化方向，逆时针变顺时针，顺时针变逆时针
for (int i = ; i < (m + ) / ; i++)
swap(points[i], points[m - i]);
} int main()
{
while (scanf("%d", &m) != EOF) {
if (m == ) break;
for (int i = ; i <= m; i++)
scanf("%lf%lf", &points[i].x, &points[i].y);
Reverse(); //由于点的顺序是逆时针输入，所以要将它改成顺时针
points[m + ] = points[]; double left = , right = inf, mid;
while ((right - left) >= eps) { //二分求半径,eps控制二分的精度
mid = (left + right) / 2.0;
r = mid; //r为内切圆半径
solve();
if (cCnt <= ) right = mid; //如果将该多边形顶点向内平移r的距离后，半平面交所得多边形为空，则说明r过大，应当适当缩小
else left = mid;
}
printf("%.6f\n", left);
}
return ;
}
2018-08-03