题目大意：
给定n，接下来n行逆时针给定小岛的n个顶点
输出岛内离海最远的点与海的距离
半平面交模板题
将整个小岛视为由许多半平面围成
那么以相同的比例缩小这些半平面
一直到缩小到一个点时 那个点就是离海最远的点
#include <cstdio>
#include <cmath>
#include <vector>
#include <algorithm>
using namespace std;
const double eps=1e-;
double add(double a,double b) {
if(abs(a+b)<eps*(abs(a)+abs(b))) return ;
return a+b;
}
struct P{
double x,y;
P(){};
P(double _x,double _y):x(_x),y(_y){};
P operator - (P p) {
return P(add(x,-p.x),add(y,-p.y)); }
P operator + (P p) {
return P(add(x,p.x),add(y,p.y)); }
P operator * (double d) {
return P(x*d,y*d); }
double dot (P p) {
return add(x*p.x,y*p.y); }
double det (P p) {
return add(x*p.y,-y*p.x); }
}p[], py[];
struct L {
P p, v; // p为直线上一点 v为单位方向向量
double ang; // 极角
L(){};
L(P _p,P _v):p(_p),v(_v){ ang=atan2(v.y,v.x); }
bool operator < (const L& b)const {
return ang<b.ang;
}
}l[], lp[];
int n;
double lenV(P p) {
return sqrt(p.dot(p));
} // 求p的长度
P NV(P p) {
double len=lenV(p);
return P(-p.y/len,p.x/len);
} // 求向量p的单位向量
P ins(L a,L b) {
return a.p+a.v*((b.v).det(a.p-b.p)/(a.v).det(b.v));
} // 求a与b的交点
bool onLeft(L l,P p) {
return (l.v).det(p-l.p)>;
} // 判断p是否在l的左侧
int insHp() {
sort(l,l+n); // 按极角排序
int head,tail;
vector <P> pi(n*); // 交点
vector <L> li(n*); // 半平面
li[head=tail=]=l[];
for(int i=;i<n;i++) {
while(head<tail && !onLeft(l[i],pi[tail-])) tail--;
while(head<tail && !onLeft(l[i],pi[head])) head++;
// 之前的半平面的交点是否都在当前半平面的左边 否则去掉
li[++tail]=l[i]; // 将当前半平面加入 if(abs((li[tail].v).det(li[tail-].v))<eps) {// 若加入后发现与上一个半平面平行
tail--; // 先把当前半平面去掉
if(onLeft(li[tail],l[i].p)) // 若当前半平面在上一个半平面左边
li[tail]=l[i]; // 说明当前半平面可将上一个覆盖
}
if(head<tail) pi[tail-]=ins(li[tail-],li[tail]);
// 加入当前半平面新产生的交点
// tail-1 是与上一个半平面产生的交点
}
while(head<tail && !onLeft(li[head],pi[tail-])) tail--;
// 当前交点是否在一开始的半平面的左边 否则说明当前被开始的半平面覆盖
if(tail-head<=) return ;
pi[tail]=ins(li[tail],li[head]); // 加入与第一个半平面的交点
int m=;
for(int i=head;i<=tail;i++)
py[m++]=pi[i]; // 将半平面的内核顶点存入
return m; // 返回顶点数
}
int main()
{
while(~scanf("%d",&n)) {
if(n==) break;
for(int i=;i<n;i++)
scanf("%lf%lf",&p[i].x,&p[i].y);
for(int i=;i<n;i++) {
lp[i].p=p[(i+)%n]-p[i];
lp[i].v=NV(lp[i].p);
}
double le=,ri=;
while(ri-le>eps) {
// 二分
double mid=le+(ri-le)/;
for(int i=;i<n;i++)
l[i]=L(p[i]+lp[i].v*mid,lp[i].p);
// 以mid比例 收缩多边形
int m=insHp();
if(!m) ri=mid;
else le=mid;
}
printf("%.6f\n",le);
}
return ;
}