BZOJ1038 [ZJOI2008]瞭望塔

题目描述#

致力于建设全国示范和谐小村庄的 $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#

1
6
2
1 2 4 5 6 7
3
1 2 2 4 2 1

Sample Output#

1
1.000

题解#

将所有的直线延长在上面做一个半平面交
答案一定取在直线的交点或下面山是顶点上

枚举半平面的每个交点向下做垂线，计算出他与山之间的距离
然后枚举山的每个顶点做垂线，计算出他与半平面之间的距离

1
#include <cstdio>
2
#include <cstring>
3
#include <algorithm>
4
#include <cmath>
5
using namespace std;
6
inline int read()
7
{
8
    int x=0,f=1;char ch=getchar();
9
    while (ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
10
    while (ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
11
    return x*f;
12
}
13
const int MAXN = 305;
14
const double eps = 1e-20;
15
struct Point
16
{
17
    double x, y;
18
    Point(double _x = 0, double _y = 0) : x(_x), y(_y) {}
19
    Point operator - (const Point &a)
20
    {
21
        return Point(x - a.x, y - a.y);
22
    }
23
    double operator * (const Point &a)
24
    {
25
        return x * a.y - y * a.x;
26
    }
27
}a[MAXN], c[MAXN];
28
struct line
29
{
30
    Point a, b;
31
    line(){}
32
    line(Point _a, Point _b)
33
    {
34
        a = _a;
35
        b = _b;
36
    }
37
    double k;
38
}l[MAXN];
39
bool cmp(line a, line b)
40
{
41
    if (a.k == b.k) return (b.a - a.a) * (b.b - a.a) >= eps;
42
    return a.k < b.k;
43
}
44
Point Get_Point(line a, line b)
45
{
46
    Point x;
47
    double dot1, dot2;
48
    dot1 = (b.a - a.a) * (b.b - a.a);
49
    dot2 = (b.b - a.b) * (b.a - a.b);
50
    x.x = (a.a.x * dot2 + a.b.x * dot1) / (dot1 + dot2);
51
    x.y = (a.a.y * dot2 + a.b.y * dot1) / (dot1 + dot2);
52
    return x;
53
}
54
bool Judge(line a, line b, line c)
55
{
56
    Point x = Get_Point(b, c);
57
    return (a.b - x) * (a.a - x) >= eps;
58
}
59
int Q[MAXN];
60
int main()
61
{
62
    int n = read();
63
    for (int i = 1; i <= n; i++)
64
        a[i].x = read();
65
    for (int i = 1; i <= n; i++)
66
        a[i].y = read();
67
    a[0].x = a[1].x - 1, a[0].y = 10000000;
68
    a[n + 1].x = a[n].x + 1, a[n + 1].y = 10000000;
69
    n++;
70
    for (int i = 1; i <= n; i++)
71
    {
72
        l[i].a = a[i - 1], l[i].b = a[i];
73
        l[i].k = atan2(a[i].y - a[i - 1].y, a[i].x - a[i - 1].x);
74
    }
75
    int cnt = 1;
76
    sort(l + 1, l + n + 1, cmp);
77
    for (int i = 2; i <= n; i++)
78
        if (l[i].k - l[i - 1].k >= eps)
79
            l[++cnt] = l[i];
80
    int h = 1, t = 2;
81
    Q[1] = 1, Q[2] = 2;
82
    for (int i = 3; i <= cnt; i++)
83
    {
84
        while (t > h && Judge(l[i], l[Q[t - 1]], l[Q[t]])) t--;
85
        while (t > h && Judge(l[i], l[Q[h + 1]], l[Q[h]])) h++;
86
        Q[++t] = i;
87
    }
88
    while (t > h && Judge(l[h], l[Q[t - 1]], l[Q[t]])) t--;
89
    while (t > h && Judge(l[t], l[Q[h + 1]], l[Q[h]])) h++;
90
    int tot = 0;
91
    for (int i = h + 1; i <= t; i++)
92
        c[++tot] = Get_Point(l[Q[i - 1]], l[Q[i]]);
93
    double ans = 1e60;
94
    for (int i = 1; i < n - 1; i++)
95
        for (int j = 1; j <= tot; j++)
96
            if (a[i].x <= c[j].x && c[j].x <= a[i + 1].x)
97
            {
98
                Point t(c[j].x, -1);
99
                ans = min(ans, c[j].y - Get_Point(line(a[i + 1], a[i]), line(c[j], t)).y);
100
            }
101
    for (int i = 1; i <= tot; i++)
102
        for (int j = 1; j < n; j++)
103
            if (c[i].x <= a[j].x && a[j].x <= c[i + 1].x)
104
            {
105
                Point t(a[j].x, -1);
106
                ans = min(ans, Get_Point(line(c[i], c[i + 1]), line(a[j], t)).y - a[j].y);
107
            }
108
    printf ("%.3f\n", ans);
109
    // while (1);
110
}