题解 UVA1396 【Most Distant Point from the Sea】
wjyyy
2019-02-20 19:34:19
## 题解：
本题求的是多边形内部任意一点到边的最小距离的最大值。
做这道题的时候只是觉得这个题有点像二分的模型，并且有合理的二分方式。上面那句话是我写题解的时候口胡出来的，由此可以知道，很多的二分题**都会在体现在题意中**，另见[NOIP 2018 赛道修建 题解](https://www.wjyyy.top/2755.html#i-2)。
因为点 $\left\{P_i\right\}$ 是逆时针给出来的，所以半平面交的可行域是向量 $\overrightarrow{P_iP_{i+1}}(i<n),\overrightarrow{P_nP_1}$（下同） 的左侧。
二分是直接二分答案，因此考虑把**每个向量向左平移 $mid$ 个单位**。平移这一操作很好完成，首先把向量逆时针旋转 $90^\circ$ ，然后放缩到原来长度 $k=|P_iP_{i+1}|$ 的 $\frac{mid}k$ 倍，得到向量 $\overrightarrow v$ 令 $P_i$ 和 $P_{i+1}$ 同时加上 $\overrightarrow v$ 即可。然后再做半平面交，`bool check()`函数的返回值为“面积大于 $0$ 为真”。
最后需要用`long double`输出。（不知道为什么`double`被卡了……）
## Code：
```cpp
#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;
}
```