题目链接：bzoj点我:-) 洛谷点我:-)
题目描述： 致力于建设全国示范和谐小村庄的H村村长dadzhi，决定在村中建立一个瞭望塔，以此加强村中的治安。 我们将H村抽象为一维的轮廓。如下图所示 
我们可以用一条山的上方轮廓折线(x1, y1), (x2, y2), …. (xn, yn)来描述H村的形状，这里x1 < x2 < …< xn。瞭望塔可以建造在[x1, xn]间的任意位置, 但必须满足从瞭望塔的顶端可以看到H村的任意位置。可见在不同的位置建造瞭望塔，所需要建造的高度是不同的。为了节省开支，dadzhi村长希望建造的塔高度尽可能小。 请你写一个程序，帮助dadzhi村长计算塔的最小高度。
输入格式： 输入文件tower.in第一行包含一个整数n，表示轮廓折线的节点数目。接下来第一行n个整数, 为x1 ~ xn. 第三行n个整数，为y1 ~ yn。
输出格式： 输出文件tower.out仅包含一个实数，为塔的最小高度，精确到小数点后三位。
思路： 首先，我们发现把每段轮廓线看作一条直线，那么所有直线左边的公共部分就是瞭望塔最终应该在的位置范围，样例如图： 
想到这里，半平面交可做了。
接下来，考虑两个相邻的端点x, x+1，可以发现它们之间的那一段答案是单峰的，所以用三分法解决即可。 单峰性的证明： 当我们讨论瞭望塔的位置在 x 和 x+1 之间时 ， 这一段区间上方的瞭望塔区间一定为一个下凸的单峰，可以分类讨论x至x+1的情况，可以发现不管是上升下降还是平的，答案都是一个单峰
（稍严谨的证明：当我们讨论瞭望塔的位置在 i 和 i+1 之间时 ， 其他的直线可以组成一个下凸的半平面 ， 将整个图形旋转使得直线水平 ， 可知下凸的半平面仍保持其性质。 那么瞭望塔的高度在此线段上保持单峰性）
感想： 三分真神奇。。 但是。还是要码一码半平面交的。。毕竟。。没写过。。
代码：
//miaomiao 2017.2.8#include<cstdio>#include<cstdlib>#include<cstring>#include<cmath>#include<algorithm>using namespace std;#define For(i, a, b) for(int i = (a); i <= (int)(b); i++)#define N (300+5)#define eps 1e-9int n;double x[N], y[N], ret, len;inline double calc(int i, double xi){ ret = 0, len = y[i]+(y[i+1]-y[i])/(x[i+1]-x[i])*(xi-x[i]); For(j, 1, n){ if(i==j || i+1==j) continue; int a = j+(j<i? 1: -1); double h = y[j]+(y[a]-y[j])/(x[a]-x[j])*(xi-x[j]); ret = max(ret, h-len); } return ret;}int main(){ scanf("%d", &n); For(i, 1, n) scanf("%lf", &x[i]); For(i, 1, n) scanf("%lf", &y[i]); double ans = 1.0*(1e20); For(i, 1, n-1){ double lm, rm, mid, L = x[i], R = x[i+1]; while(fabs(R-L) > eps){ mid = (R-L)/3.0; lm = L+mid, rm = R-mid; if(calc(i, lm) > calc(i, rm)) L = lm; else R = rm; } ans = min(ans, calc(i, L)); } if(n == 1) ans = 0; PRintf("%.3lf/n", ans); return 0;}新闻热点
疑难解答
