[文章目录]
Description
致力于建设全国示范和谐小村庄的H村村长dadzhi，决定在村中建立一个瞭望塔，以此加强村中的治安。我们将H村抽象为一维的轮廓。如下图所示 我们可以用一条山的上方轮廓折线(x1, y1), (x2, y2), …. (xn, yn)来描述H村的形状，这里x1 < x2 < …< xn。瞭望塔可以建造在[x1, xn]间的任意位置, 但必须满足从瞭望塔的顶端可以看到H村的任意位置。可见在不同的位置建造瞭望塔，所需要建造的高度是不同的。为了节省开支，dadzhi村长希望建造的塔高度尽可能小。请你写一个程序，帮助dadzhi村长计算塔的最小高度。
半平面交，求出可以瞭望到H村所有地方的位置，答案肯定在求出的凸包的边缘上，凸包边缘为分段一次函数，村子轮廓也是一次函数。
两个分段一次函数的差的极值一定在分段端点处取得。
按照x从小到大扫一遍即可。
#include <cmath>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
#define eps 1e-10
#define N 400
typedef long double dl;
const long double inf=1e25;
int n,m;
struct point
{
dl x,y;
point(){}
point(dl _x,dl _y){x=_x,y=_y;}
point operator +(const point &z)const {return point(x+z.x,y+z.y);}
point operator -(const point &z)const {return point(x-z.x,y-z.y);}
point operator *(const dl z)const {return point(x*z,y*z);}
dl operator *(const point &z)const {return x*z.y-y*z.x;}
}a[N],b[N];
bool cmp1(point x,point y){return x.x<y.x;}
struct line
{
point p,v;
dl a;
line(){}
line(point x,point y){p=x,v=y,a=atan2(v.y,v.x);}
}l[N];
point getpo(line l1,line l2)
{
point u=l1.p-l2.p;
dl t=(l2.v*u)/(l1.v*l2.v);
return l1.p+l1.v*t;
}
bool onlft(line x,point y)
{
return x.v*(y-x.p)>eps;
}
bool cmp(line x,line y)
{
return fabs(x.a-y.a)<eps ? onlft(x,y.p) : x.a<y.a;
}
void half_plane()
{
sort(l+1,l+n+1,cmp);
static int q[N]; int i,h,t=1;
for(i=2;i<=n;++i) if(fabs(l[i].a-l[t].a)>eps) l[++t]=l[i];
n=t; h=t=q[1]=1;
for(i=2;i<=n;++i)
{
while(h<t&&onlft(l[i],getpo(l[q[t]],l[q[t-1]]))) --t;
while(h<t&&onlft(l[i],getpo(l[q[h]],l[q[h+1]]))) ++h;
q[++t]=i;
}
while(h<t&&onlft(l[q[h]],getpo(l[q[t]],l[q[t-1]]))) --t;
while(h<t&&onlft(l[q[t]],getpo(l[q[h]],l[q[h+1]]))) ++h;
q[++t]=q[h]; n=0;
for(i=h;i<t;++i) b[++n]=getpo(l[q[i]],l[q[i+1]]);
sort(b+1,b+n+1,cmp1);
}
dl gety(dl x,point p,point v) {return (v.y-p.y)/(v.x-p.x)*(x-p.x)+p.y;}
int main()
{
scanf("%d",&n); m=n; int i;
for(i=1;i<=n;++i) scanf("%Lf",&a[i].x);
for(i=1;i<=n;++i) scanf("%Lf",&a[i].y);
for(i=1;i<n;++i) l[i]=line(a[i+1],a[i]-a[i+1]);
l[n]=line(a[1],point(-eps,1));
l[n+1]=line(point(a[n].x+eps,inf),point(eps,-1));
++n;
half_plane();
int i1=1,i2=1;
dl ans=inf;
while(i1<=n&&i2<=m)
{
if(fabs(b[i1].x-a[i2].x)<eps) ans=min(ans,fabs(b[i1].y-a[i2].y)),i1++,i2++;
if(b[i1].x<a[i2].x) ans=min(ans,fabs(b[i1].y-gety(b[i1].x,a[i2-1],a[i2]))),i1++;
else ans=min(ans,fabs(a[i2].y-gety(a[i2].x,b[i1-1],b[i1]))),i2++;
}
printf("%.3Lf",ans);
return 0;
}