2019-02-20 19:34:19

## Code：

#include<cmath>
#include<cstdio>
#include<cstring>
#include<algorithm>
#define db long double
#define eps 1e-10
struct pnt
{
db x,y;
pnt(db x,db y)
{
this->x=x;
this->y=y;
}
pnt(){}
friend pnt operator +(pnt a,pnt b)
{return pnt(a.x+b.x,a.y+b.y);}
friend pnt operator -(pnt a,pnt b)
{return pnt(a.x-b.x,a.y-b.y);}
friend db operator *(pnt a,pnt b)
{return a.x*b.y-a.y*b.x;}
pnt times(db k)
{return pnt(x*k,y*k);}
db len()
{return sqrt(x*x+y*y);}
}p[105],t[105];
struct seg
{
pnt a,b;
db d;
seg(pnt a,pnt b)
{
this->a=a;
this->b=b;
d=atan2((b-a).y,(b-a).x);
}
seg(){}
friend bool operator <(seg x,seg y)
{
if(fabs(x.d-y.d)>eps)
return x.d<y.d;
return (y.a-x.a)*(y.b-x.a)>eps;
}
friend bool operator !=(seg x,seg y)
{return fabs(x.d-y.d)>eps;}
}s[105],f[105],q[105];
pnt its(seg x,seg y)
{
db u=(y.a-x.a)*(y.b-x.a);
db d=u+(y.b-x.b)*(y.a-x.b);
return x.a+(x.b-x.a).times(u/d);
}
int n;
bool check(db k)
{
for(int i=1;i<=n;++i)
{
db R=(s[i].b-s[i].a).len();
pnt v(-(s[i].b-s[i].a).y,(s[i].b-s[i].a).x);
v=v.times(k/R);
f[i]=seg(s[i].a+v,s[i].b+v);
}
std::sort(f+1,f+1+n);
int l=0,r=0;
for(int i=1;i<=n;++i)
if(f[i]!=f[i-1])
{
while(r-l>1&&(f[i].b-t[r])*(f[i].a-t[r])>-eps)
--r;
while(r-l>1&&(f[i].b-t[l+2])*(f[i].a-t[l+2])>-eps)
++l;
q[++r]=f[i];
if(r-l>1)
t[r]=its(q[r],q[r-1]);
}
while(r-l>1&&(q[l+1].b-t[r])*(q[l+1].a-t[r])>eps)
--r;
t[l+1]=its(q[l+1],q[r]);
db sum=t[r]*t[l+1];
for(int i=l+1;i<r;++i)
sum+=t[i]*t[i+1];
return sum>eps;
}
int main()
{
scanf("%d",&n);
f[0].d=233;
while(n)
{
for(int i=1;i<=n;++i)
{
scanf("%Lf%Lf",&p[i].x,&p[i].y);
if(i>1)
s[i]=seg(p[i-1],p[i]);
}
1[s]=seg(p[n],p[1]);
db l=0,r=5000,mid;
while(r-l>1e-9)
{
mid=(l+r)/2;
if(check(mid))
l=mid;
else
r=mid;
}
printf("%.8Lf\n",l);
scanf("%d",&n);
}
return 0;
}
• star
首页