题目描述
致力于建设全国示范和谐小村庄的$H$村村长$dadzhi$，决定在村中建立一个瞭望塔，以此加强村中的治安。
我们将$H$村抽象为一维的轮廓。如下图所示
我们可以用一条山的上方轮廓折线$(x_1, y_1)$, $(x_2, y_2)$, $…$ $(x_n, y_n)$来描述H村的形状，这里$x_1 < x_2 < … < x_n$。瞭望塔可以建造在$[x_1, x_n]$间的任意位置, 但必须满足从瞭望塔的顶端可以看到$H$村的任意位置。可见在不同的位置建造瞭望塔，所需要建造的高度是不同的。为了节省开支，$dadzhi$村长希望建造的塔高度尽可能小。
请你写一个程序，帮助$dadzhi$村长计算塔的最小高度。
输入格式：
输入文件$tower.in$第一行包含一个整数n，表示轮廓折线的节点数目。接下来第一行n个整数, 为$x_1 ~ x_n$. 第三行n个整数，为$y_1 ~ y_n$。
输出格式：
输出文件$tower.out$仅包含一个实数，为塔的最小高度，精确到小数点后三位。
Sample Input
6
1 2 4 5 6 7
1 2 2 4 2 1
Sample Output
1.000
题解
将所有的直线延长在上面做一个半平面交
答案一定取在直线的交点或下面山是顶点上
枚举半平面的每个交点向下做垂线，计算出他与山之间的距离
然后枚举山的每个顶点做垂线，计算出他与半平面之间的距离
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>
using namespace std;
inline int read()
{
int x=0,f=1;char ch=getchar();
while (ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
while (ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
return x*f;
}
const int MAXN = 305;
const double eps = 1e-20;
struct Point
{
double x, y;
Point(double _x = 0, double _y = 0) : x(_x), y(_y) {}
Point operator - (const Point &a)
{
return Point(x - a.x, y - a.y);
}
double operator * (const Point &a)
{
return x * a.y - y * a.x;
}
}a[MAXN], c[MAXN];
struct line
{
Point a, b;
line(){}
line(Point _a, Point _b)
{
a = _a;
b = _b;
}
double k;
}l[MAXN];
bool cmp(line a, line b)
{
if (a.k == b.k) return (b.a - a.a) * (b.b - a.a) >= eps;
return a.k < b.k;
}
Point Get_Point(line a, line b)
{
Point x;
double dot1, dot2;
dot1 = (b.a - a.a) * (b.b - a.a);
dot2 = (b.b - a.b) * (b.a - a.b);
x.x = (a.a.x * dot2 + a.b.x * dot1) / (dot1 + dot2);
x.y = (a.a.y * dot2 + a.b.y * dot1) / (dot1 + dot2);
return x;
}
bool Judge(line a, line b, line c)
{
Point x = Get_Point(b, c);
return (a.b - x) * (a.a - x) >= eps;
}
int Q[MAXN];
int main()
{
int n = read();
for (int i = 1; i <= n; i++)
a[i].x = read();
for (int i = 1; i <= n; i++)
a[i].y = read();
a[0].x = a[1].x - 1, a[0].y = 10000000;
a[n + 1].x = a[n].x + 1, a[n + 1].y = 10000000;
n++;
for (int i = 1; i <= n; i++)
{
l[i].a = a[i - 1], l[i].b = a[i];
l[i].k = atan2(a[i].y - a[i - 1].y, a[i].x - a[i - 1].x);
}
int cnt = 1;
sort(l + 1, l + n + 1, cmp);
for (int i = 2; i <= n; i++)
if (l[i].k - l[i - 1].k >= eps)
l[++cnt] = l[i];
int h = 1, t = 2;
Q[1] = 1, Q[2] = 2;
for (int i = 3; i <= cnt; i++)
{
while (t > h && Judge(l[i], l[Q[t - 1]], l[Q[t]])) t--;
while (t > h && Judge(l[i], l[Q[h + 1]], l[Q[h]])) h++;
Q[++t] = i;
}
while (t > h && Judge(l[h], l[Q[t - 1]], l[Q[t]])) t--;
while (t > h && Judge(l[t], l[Q[h + 1]], l[Q[h]])) h++;
int tot = 0;
for (int i = h + 1; i <= t; i++)
c[++tot] = Get_Point(l[Q[i - 1]], l[Q[i]]);
double ans = 1e60;
for (int i = 1; i < n - 1; i++)
for (int j = 1; j <= tot; j++)
if (a[i].x <= c[j].x && c[j].x <= a[i + 1].x)
{
Point t(c[j].x, -1);
ans = min(ans, c[j].y - Get_Point(line(a[i + 1], a[i]), line(c[j], t)).y);
}
for (int i = 1; i <= tot; i++)
for (int j = 1; j < n; j++)
if (c[i].x <= a[j].x && a[j].x <= c[i + 1].x)
{
Point t(a[j].x, -1);
ans = min(ans, Get_Point(line(c[i], c[i + 1]), line(a[j], t)).y - a[j].y);
}
printf ("%.3f\n", ans);
// while (1);
}