poj3525 半面交+二分
//题目链接：http://poj.org/problem?id=3525
//题目意思：求在一个形状为多边形的岛中的一点到海的最大距离
//解题思路：
//有一种方法:二分距离，再求半面交
//这里需要注意的是精度问题，长度要从0～10^9二分（好像很多对长度的二分都是10^9的），eps 1e-11
//212K 32ms 代码如下：
#include<iostream>#include<cstdio>#include<math.h>#define eps 1e-11using namespace std;const int MAXN=202;struct point {double x,y;};point points[MAXN],p[MAXN],q[MAXN];int n;bool zero(double x){ return x>0? x<eps:x>-eps;}double xmult(point p1,point p2,point p0){ return (p1.x-p0.x)*(p2.y-p0.y)-(p2.x-p0.x)*(p1.y-p0.y);}int same_side(point p1,point p2,point l1,point l2){ return xmult(l1,p1,l2)*xmult(l1,p2,l2)>eps;}point intersection(point p1,point p2,point p3,point p4){ point ret=p1; double t=((p1.x-p3.x)*(p3.y-p4.y)-(p3.x-p4.x)*(p1.y-p3.y)) /((p1.x-p2.x)*(p3.y-p4.y)-(p3.x-p4.x)*(p1.y-p2.y)); ret.x+=t*(p2.x-p1.x); ret.y+=t*(p2.y-p1.y); return ret;}void polygon_cut(int &n,point *p,point l1,point l2,point side){ point pp[1000]; int m=0,i; for(i=0;i<n;i++) { if(same_side(p[i],side,l1,l2)) pp[m++]=p[i]; if(!same_side(p[i],p[(i+1)%n],l1,l2) &&!(zero(xmult(p[i],l1,l2)) &&zero(xmult(p[(i+1)%n],l1,l2)))) pp[m++]=intersection(p[i],p[(i+1)%n],l1,l2); } n=0; for(i=0;i<m;i++) if(!i||!zero(pp[i].x-pp[i-1].x)||!zero(pp[i].y-pp[i-1].y)) p[n++]=pp[i]; if(zero(p[n-1].x-p[0].x)&&zero(p[n-1].y-p[0].y)) n--;// }double distance(point p1,point p2){ return sqrt((p1.x-p2.x)*(p1.x-p2.x)+(p1.y-p2.y)*(p1.y-p2.y));}void slove(double dis,int &m){ int i; for(i=0;i<n;i++) { point side; //向内推进dis point s=points[i],e=points[(i+1)%n]; double xx=e.x-s.x,yy=e.y-s.y; double dd=sqrt(xx*xx+yy*yy); s.x+=dis*(-yy)/dd; s.y+=dis*(xx)/dd; e.x+=dis*(-yy)/dd; e.y+=dis*(xx)/dd; side.x=s.x-yy; side.y=s.y+xx; polygon_cut(m,p,s,e,side); }}double two(double l,double r){ double mid=(l+r)/2.0; if(r-l<eps)return mid; int i; for(i=0;i<n;i++)p[i]=points[i]; int m=n; slove(mid,m); if(m<3)return two(l,mid); else { return two(mid,r); }}int main(){ while(scanf("%d",&n),n) { int i; for(i=0;i<n;i++) { scanf("%lf%lf",&points[i].x,&points[i].y); } double res=0.0; res=two(0,1000000000); printf("%.6lf\n",res); } return 0;}