poj3525 半面交+二分
//题目意思：求在一个形状为多边形的岛中的一点到海的最大距离
//解题思路：
//有一种方法:二分距离，再求半面交
//这里需要注意的是精度问题，长度要从0～10^9二分（好像很多对长度的二分都是10^9的），eps 1e-11
//212K 32ms 代码如下：
[cpp]
#include<iostream>
#include<cstdio>
#include<math.h>
#define eps 1e-11
using 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;
}
作者：ssslpk
补充：软件开发 , C++ ,
