致力于建设全国示范和谐小村庄的H村村长dadzhi，决定在村中建立一个瞭望塔。 我们将H村抽象为一维的轮廓。 我们可以用一条山的上方轮廓折线(x1, y1), (x2, y2), …. (xn, yn)来描述，x1 < x2 < …< xn。 瞭望塔可以建造在[x1, xn]间的任意位置, 但必须满足从瞭望塔的顶端可以看到H村的任意位置。 请你写一个程序，帮助dadzhi村长计算塔的最小高度。
刚开始看了半天还没看懂样例，后来才知道，我以为塔是建在x=0上的，其实是在轮廓折线上……我好智障…….. 先不管塔高，考虑要看到某一线段，塔顶必须是在线段所在直线的上方。 显然求一下半平面交即可得到一个下凸的凸壳，在他上方的区域即是塔顶合法位置。 那么如何求塔高呢？ 其实我们只需要每枚举在所有折点位置造塔即可，这里说的折点包括轮廓折线上的折点和凸壳上的折点。 这样一定包含最优高度，道理太显然了。
代码借鉴了Claris巨神。自己写的可能是由于精度问题一直wa。
#include<cstdio> #include<algorithm> #include<cstring> #include<cmath> #define eps 1e-7 using namespace std; const int maxn=305; struct Point{ double x,y; } p[maxn],t; struct Line{ double k,b; void init(Point A,Point B) { k=(A.y-B.y)/(A.x-B.x); b=B.y-k*B.x; } } L[maxn],stk[maxn]; int n,top; double res=1e+50; bool my_cmp(Line A,Line B){ if(abs(A.k-B.k)<eps) return A.b<B.b; return A.k<B.k; } Point inter(Line A,Line B){ Point res; res.x=(B.b-A.b)/(A.k-B.k); res.y=A.k*res.x+A.b; return res; } double f(double x){ double res=0; for(int i=1;i<=top;i++) res=max(res,stk[i].k*x+stk[i].b); return res; } double g(double x){ int i; for(i=n;i&&x<p[i].x;i--); return p[i].y+(x-p[i].x)/(p[i+1].x-p[i].x)*(p[i+1].y-p[i].y); } int main() { freopen("bzoj1038.in","r",stdin); freopen("bzoj1038.out","w",stdout); scanf("%d",&n); for(int i=1;i<=n;i++) scanf("%lf",&p[i].x); for(int i=1;i<=n;i++) scanf("%lf",&p[i].y); for(int i=1;i<=n-1;i++) L[i].init(p[i],p[i+1]); sort(L+1,L+n,my_cmp); for(int i=1;i<=n-1;i++) if(i==n-1||abs(L[i].k-L[i+1].k)>eps){ while(top>=2&&inter(stk[top],L[i]).x<inter(stk[top-1],stk[top]).x) top--; stk[++top]=L[i]; } for(int i=1;i<=n;i++) res=min(res,f(p[i].x)-p[i].y); for(int i=1;i<=top-1;i++) { Point now=inter(stk[i],stk[i+1]); res=min(res,now.y-g(now.x)); } printf("%.3lf\n",res); return 0; }