题目描述
致力于建设全国示范和谐小村庄的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仅包含一个实数，为塔的最小高度，精确到小数点后三位。
输入输出样例
输入 #1
6
1 2 4 5 6 7
1 2 2 4 2 1
输出 #1
1.000
说明/提示
对于60%的数据， N ≤ 60；
对于100%的数据， N ≤ 300，输入坐标绝对值不超过106，注意考虑实数误差带来的问题。
题解
先做一遍半平面交，由于必定是无界的，我在左右和上侧各加了一个半平面（做完之后把不需要的边界去掉）。
这样我们就得到了一个下凸壳，如果瞭望塔建在x0这个位置，那么必定是建到直线x=x与这个凸壳的交点的高度即可。然后考虑到高度是由上下共同决定的，经过显而易见的贪心，
可以发现瞭望塔的横坐标要么是这个凸壳上的顶点，要么是下方轮廓线的端点，O(n)扫一遍即可。总复杂度O(nlogn)。
#include<bits/stdc++.h>//半平面交 #define ll long long using namespace std; const double M = 1e15; const int N = 1010; struct P { double x, y; } s[N], p[N]; int cnt = 0; struct L { P a, b; double val; } t[N], q[N]; P operator-(P a, P b) { P t; t.x = a.x - b.x; t.y = a.y - b.y; return t; } double operator*(P a, P b) { return a.x * b.y - a.y * b.x; } double ans = 1e15; bool operator<(L a, L b) { if (a.val == b.val)return (a.b - a.a) * (b.b - a.a) > 0; return a.val < b.val; } P inter(L a, L b) { double k1, k2, t; k1 = (b.b - a.a) * (a.b - a.a); k2 = (a.b - a.a) * (b.a - a.a); t = k1 / (k1 + k2); P ans; ans.x = b.b.x + (b.a.x - b.b.x) * t; ans.y = b.b.y + (b.a.y - b.b.y) * t; return ans; } double dist(L a, P b) { double c = (a.a.y - a.b.y) / (a.a.x - a.b.x); double d = c * (b.x - a.a.x) + a.a.y; return fabs(b.y - d); } bool check(L a, L b, L c) { P p = inter(a, b); return (c.b - c.a) * (p - c.a) < 0; } void fun() { sort(t + 1, t + 1 + cnt); int l = 1, r = 0; int tot = 0; for (int i = 1; i <= cnt; i++) { if (t[i].val != t[i - 1].val)tot++; t[tot] = t[i]; } cnt = tot; q[++r] = t[1], q[++r] = t[2]; for (int i = 3; i <= cnt; i++) { while (l < r && check(q[r - 1], q[r], t[i]))r--; while (l < r && check(q[l + 1], q[l], t[i]))l++; q[++r] = t[i]; } while (l < r && check(q[r - 1], q[r], q[l]))r--; while (l < r && check(q[l + 1], q[l], q[r]))l++; q[r + 1] = q[l]; cnt = 0; for (int i = l; i <= r; i++) { P o = inter(q[i], q[i + 1]); p[++cnt] = o; } } bool cmp(P a, P b) { if (a.x == b.x) return a.y < b.y; return a.x < b.x; } int main() { ios::sync_with_stdio(false); cin.tie(0); int n; cin >> n; for (int i = 1; i <= n; i++)cin >> s[i].x; for (int i = 1; i <= n; i++)cin >> s[i].y; t[++cnt].a = {s[1].x, M}, t[cnt].b = {s[1].x, 0}; t[cnt].val = atan2(-M, 0); t[++cnt].a = {s[n].x, 0}, t[cnt].b = {s[n].x, M}; t[cnt].val = atan2(M, 0); t[++cnt].a = {M, M}, t[cnt].b = {0, M}; t[cnt].val = atan2(0, -M); for (int i = 1; i < n; i++) { t[++cnt].a = s[i], t[cnt].b = s[i + 1]; t[cnt].val = atan2(s[i + 1].y - s[i].y, s[i + 1].x - s[i].x); } fun(); sort(p + 1, p + 1 + cnt, cmp); int tot = 0; for (int i = 1; i <= cnt; i++) { if (p[i].x == p[tot].x)continue; p[++tot] = p[i]; } cnt = tot; int i = 1, j = 1; p[0].x = p[1].x - 1; p[0].y = p[1].y;//避免第一个不相等的情况 while (i <= cnt && j <= n) { if (p[i].x == s[j].x) { ans = min(ans, p[i].y - s[j].y); i++, j++; } else if (p[i].x < s[j].x) { L c; c.a = s[j], c.b = s[j - 1]; ans = min(ans, dist(c, p[i])); i++; } else if (p[i].x > s[j].x) { L c; c.a = p[i], c.b = p[i - 1]; ans = min(ans, dist(c, s[j])); j++; } } cout << fixed << setprecision(3) << ans << endl; return 0; }