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
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
1.000
【输出样例二】
14.500
HINT
N ≤ 300，输入坐标绝对值不超过106，注意考虑实数误差带来的问题。
题解
可以发现，答案必定在任意两点连线的上方（不然会挡住视线）。
再进一步，可以发现答案只要满足在任意相邻两点上方，就一定满足上述条件。
因此只需要求出$n-1$个半平面的交，再枚举在已知点或半平面交点处建筑瞭望塔即可。
附代码：
#include <algorithm>
#include <cstdio>
using std::min;
using std::max;
const double eps = 1e-6;
int cmp(double l) {
if (l > eps) return 1;
if (l < eps) return -1;
return 0;
}
struct Point{
double x, y;
};
struct Line{
double k, b;
Line() : k(.0), b(.0) {}
Line(const Point &a, const Point &b) {
k = (a.y - b.y) / (a.x - b.x);
this->b = a.y - a.x * k;
}
friend inline bool operator<(const Line &a, const Line &b) {
if (cmp(a.k - b.k)) return a.k < b.k;
return a.b > b.b;
}
double operator()(double x) const {
return k * x + b;
}
};
double crossing(const Line &a, const Line &b) {
return (a.b - b.b) / (b. k - a.k);
}
const int N = 305;
Point p[N];
Line l[N], s[N];
int main() {
int n;
scanf("%d", &n);
for (int i = 0; i < n; ++i) scanf("%lf", &p[i].x);
for (int i = 0; i < n; ++i) scanf("%lf", &p[i].y);
for (int i = 1; i < n; ++i) l[i - 1] = Line(p[i - 1], p[i]);
std::sort(l, l + n - 1);
int m = 0;
for (int i = 0; i < n - 1; ++i) {
while (m > 1 && crossing(s[m - 1], l[i]) <= crossing(s[m - 1], s[m - 2])) --m;
s[m++] = l[i];
}
double ans = 1e10;
int j = 0;
for (int i = 0; i < n; ++i) {
while (j < m - 1 && p[i].x > crossing(s[j], s[j + 1])) ++j;
ans = min(ans, s[j](p[i].x) - p[i].y);
}
j = 1;
for (int i = 0; i < m - 1; ++i) {
double x = crossing(s[i], s[i + 1]);
if (x > p[n - 1].x) break;
while (p[j].x < x) ++j;
ans = min(ans, s[i](x) - Line(p[j - 1], p[j])(x));
}
printf("%.3lfn", ans);
return 0;
}
（写了一遍一直调了一个小时没有A。。。重写一遍A。。。）
内容来源于网络如有侵权请私信删除
- 还没有人评论，欢迎说说您的想法！
客服
