NekoMio's Blog

美しいものが起こることを常に信じている

  1. 1. 题目描述
  2. 2. 输入格式:
  3. 3. 输出格式:
  4. 4. Sample Input
  5. 5. Sample Output
  • 题解
  • 题目描述

    致力于建设全国示范和谐小村庄的$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
    2
    3
    6
    1 2 4 5 6 7
    1 2 2 4 2 1

    Sample Output

    1
    1.000

    题解

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

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

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    33
    34
    35
    36
    37
    38
    39
    40
    41
    42
    43
    44
    45
    46
    47
    48
    49
    50
    51
    52
    53
    54
    55
    56
    57
    58
    59
    60
    61
    62
    63
    64
    65
    66
    67
    68
    69
    70
    71
    72
    73
    74
    75
    76
    77
    78
    79
    80
    81
    82
    83
    84
    85
    86
    87
    88
    89
    90
    91
    92
    93
    94
    95
    96
    97
    98
    99
    100
    101
    102
    103
    104
    105
    106
    107
    108
    109
    110
    #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);
    }

    本文作者 : NekoMio
    知识共享署名-非商业性使用-相同方式共享 4.0 国际许可协议进行许可。
    本文链接 : https://www.nekomio.com/2018/03/09/136/

    本文最后更新于 天前,文中所描述的信息可能已发生改变