【BZOJ1038】[ZJOI2008]瞭望塔

Description

　　致力于建设全国示范和谐小村庄的H村村长dadzhi，决定在村中建立一个瞭望塔，以此加强村中的治安。我们将H村抽象为一维的轮廓。如下图所示我们可以用一条山的上方轮廓折线(x1, y1), (x2, y2), …. (xn, yn)来描述H村的形状，这里x1 < x2 < …< xn。瞭望塔可以建造在[x1, xn]间的任意位置, 但必须满足从瞭望塔的顶端可以看到H村的任意位置。可见在不同的位置建造瞭望塔，所需要建造的高度是不同的。为了节省开支，dadzhi村长希望建造的塔高度尽可能小。请你写一个程序，帮助dadzhi村长计算塔的最小高度。

Input

　　第一行包含一个整数n，表示轮廓折线的节点数目。接下来第一行n个整数, 为x1 ~ xn. 第三行n个整数，为y1 ~ yn。

Output

　　仅包含一个实数，为塔的最小高度，精确到小数点后三位。

Sample Input

【输入样例一】
6
1 2 4 5 6 7
1 2 2 4 2 1
【输入样例二】
4
10 20 49 59
0 10 10 0

Sample Output

【输出样例一】
1.000
【输出样例二】
14.500

HINT

N ≤ 300，输入坐标绝对值不超过106，注意考虑实数误差带来的问题。

题解：首先能看到所有位置的点一定在这些折线的上半平面交上，现在问题就变成了在半平面交和下面的折线上各选择一个横坐标相同的点使得两点间距离最小。因为上下都是折线，那么最小值一定是在某个折线的拐点处取到，那么只需要将这些拐点都扫一遍即可。

为了方便，我们需要添加3条辅助线（上，左，右）来限制边界，注意3条线的斜率不能相同。

#include <cstdio>

#include <iostream>

#include <algorithm>

#include <cmath>

using namespace std;

typedef long double ld;

const int maxn=310;

const ld eps=1e-10;

int n,m,h,t;

int q[maxn];

ld ans;

struct point

{

	ld x,y;

	point (){}

	point (ld a,ld b){x=a,y=b;}

	point operator + (const point &a) const {return point(x+a.x,y+a.y);}

	point operator - (const point &a) const {return point(x-a.x,y-a.y);}

	ld operator * (const point &a) const {return x*a.y-y*a.x;}

	point operator * (const ld &a) const {return point(x*a,y*a);}

}v[maxn],p[maxn];

struct line

{

	point p,v;

	ld a;

	line() {}

	line(point x,point y) {p=x,v=y,a=atan2(v.y,v.x);}

}l[maxn];

point getp(line l1,line l2)

{

	point u=l1.p-l2.p;

	ld temp=(l2.v*u)/(l1.v*l2.v);

	return l1.p+l1.v*temp;

}

bool onlft(line a,point b)

{

	return a.v*(b-a.p)>eps;

}

bool cmpl(line a,line b)

{

	if(fabs(a.a-b.a)<eps)	return onlft(a,b.p);

	return a.a<b.a;

}

bool cmpp(point a,point b)

{

	return a.x<b.x;

}

void HPI()

{

	sort(l+1,l+n+3,cmpl);

	int i,cnt=0;

	for(i=2,cnt=1;i<=n+2;i++)	if(fabs(l[i].a-l[cnt].a)>eps)	l[++cnt]=l[i];

	h=t=q[1]=1;

	for(i=2;i<=cnt;i++)

	{

		while(h<t&&onlft(l[i],getp(l[q[t]],l[q[t-1]])))	t--;

		while(h<t&&onlft(l[i],getp(l[q[h]],l[q[h+1]])))	h++;

		q[++t]=i;

	}

	while(h<t&&onlft(l[q[h]],getp(l[q[t]],l[q[t-1]])))	t--;

	while(h<t&&onlft(l[q[t]],getp(l[q[h]],l[q[h+1]])))	h++;

	q[++t]=q[h];

	for(i=h;i<t;i++)	p[++m]=getp(l[q[i]],l[q[i+1]]);

	sort(p+1,p+m+1,cmpp);

}

void calc(point x,point a,point b)

{

	point c;

	if(fabs(x.x-a.x)<eps)	c=a;

	else	c=a+(b-a)*((x.x-a.x)/(b.x-a.x));

	ld dis=fabs(c.y-x.y);

	ans=min(ans,dis);

}

inline int rd()

{

	int ret=0,f=1;	char gc=getchar();

	while(gc<'0'||gc>'9')	{if(gc=='-')f=-f;	gc=getchar();}

	while(gc>='0'&&gc<='9')	ret=ret*10+gc-'0',gc=getchar();

	return ret*f;

}

int main()

{

	n=rd();

	int i,j;

	for(i=1;i<=n;i++)	v[i].x=rd();

	for(i=1;i<=n;i++)	v[i].y=rd();

	for(i=1;i<n;i++)	l[i]=line(v[i+1],v[i]-v[i+1]);

	l[n].p=point(0,1e25),l[n].v=point(1e7,1);

	l[n+1].p=point(-1,0),l[n+1].v=point(1,1e25);

	l[n+2].p=point(1e7,1e25),l[n+2].v=point(-1e25,-2);

	HPI(),ans=1e25;

	for(i=1,j=2;i<=n;i++)

	{

		for(;p[j].x<v[i].x;j++)

			calc(p[j],v[i-1],v[i]);

		if(j>2)

			calc(v[i],p[j-1],p[j]);

	}

	printf("%.3Lf",ans);

	return 0;

}

瞭望塔