[ZJOI 2008] 瞭望塔

发表于2017-05-09更新于2020-08-06

题目大意

村子可由一条山的上方轮廓折线 (x1,y1),  (x2,y2),  …  (xn,yn)(x_1, y_1), \; (x2, y2), \; \dots \; (x_n, y_n) 来描述（x1<x2<⋯<xnx_1 < x_2 < \dots < x_n）。瞭望塔可以建造在 [x1,xn][x_1, x_n] 间的任意位置，但必须满足从瞭望塔的顶端可以看到村子的任意位置。求塔的最小高度。

1⩽n⩽3001 \leqslant n \leqslant 300

∣x∣,  ∣y∣⩽1,000,000|x|, \; |y| \leqslant 1,000,000

题目链接

【ZJOI 2008】瞭望塔 - Luogu 2600

题解

半平面交。

对于描述村子的折线中的每一段，都必须满足塔顶在线段所在直线以上。在两侧加两个竖直的辅助直线，求半平面交，塔顶一定在其上；要使塔最低，塔顶就在半平面交得到的下边界上。

由于边界与村子都是分段一次函数，易知答案一定在分段的位置上，枚举分段点更新答案。

代码

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
#include <cstdio>
#include <cfloat>
#include <cmath>
#include <algorithm>
const int MAXN = 305;
const double EPS = 1e-14;
int dcmp(double x) {
    if (fabs(x) <= EPS) return 0;
    if (x > EPS) return 1;
    return -1;
}
struct Point {
    double x, y;
    Point(double x = 0, double y = 0) : x(x), y(y) {}
    friend Point operator+(const Point &a, const Point &b) {
        return Point(a.x + b.x, a.y + b.y);
    }
    friend Point operator-(const Point &a, const Point &b) {
        return Point(a.x - b.x, a.y - b.y);
    }
    friend Point operator*(const Point &p, const double a) {
        return Point(p.x * a, p.y * a);
    }
    friend double cross(const Point &a, const Point &b) {
        return a.x * b.y - a.y * b.x;
    }
} P[MAXN], hpi[MAXN];
struct Line {
    Point p, v;
    double slop;
    Line() {}
    Line(const Point &p, const Point &v) : p(p), v(v) {
        slop = atan2(v.y, v.x);
    }
    Point getVal(double t) const {
        return p + v * t;
    }
    bool operator<(const Line &another) const {
        return slop < another.slop || (slop == another.slop && v.x
            && getVal(-p.x / v.x).y > getVal(-another.p.x / another.v.x).y);
    }
    friend Point getIntersection(const Line &a, const Line &b) {
        double t = cross(b.v, a.p - b.p) / cross(a.v, b.v);
        return a.getVal(t);
    }
} L[MAXN];
int n;
int halfplaneIntersection() {
    int cnt = 0;
    L[cnt++] = L[0];
    for (int i = 1; i <= n; i++) {
        if (dcmp(L[i].slop - L[i - 1].slop)) L[cnt++] = L[i];
    }
    std::sort(L, L + cnt);
    static Line q[MAXN];
    static Point p[MAXN];
    int l = 0, r = 0;
    q[l] = L[0];
    for (int i = 1; i < cnt; i++) {
        while (l < r && dcmp(cross(L[i].v, p[r - 1] - L[i].p)) < 0) r--;
        while (l < r && dcmp(cross(L[i].v, p[l] - L[i].p)) < 0) l++;
        q[++r] = L[i];
        if (l < r) p[r - 1] = getIntersection(q[r - 1], q[r]);
    }
    while (l < r && dcmp(cross(q[l].v, p[r - 1] - q[l].p)) < 0) r--;
    while (l < r && dcmp(cross(q[r].v, p[l] - q[r].p)) < 0) l++;
    if (r - l <= 1) return 0;
    cnt = 0;
    for (int i = l; i < r; i++) hpi[++cnt] = p[i];
    return cnt;
}
int main() {
    scanf("%d", &n);
    for (int i = 1; i <= n; i++) scanf("%lf", &P[i].x);
    for (int i = 1; i <= n; i++) scanf("%lf", &P[i].y);
    P[0] = Point(P[1].x, P[1].y + 1);
    P[n + 1] = Point(P[n].x, P[n].y + 1);
    for (int i = 0; i <= n; i++) L[i] = Line(P[i], P[i + 1] - P[i]);
    int m = halfplaneIntersection();
    double ans = DBL_MAX;
    for (int i = 1; i <= m; i++) for (int j = 1; j < n; j++) {
        Point t(hpi[i].x, -1);
        if (P[j].x <= hpi[i].x && hpi[i].x <= P[j + 1].x)
            ans = std::min(ans, hpi[i].y - getIntersection(Line(P[j], P[j + 1] - P[j]), Line(t, hpi[i] - t)).y);
    }
    for (int i = 1; i <= n; i++) for (int j = 1; j < m; j++) {
        Point t(P[i].x, -1);
        if (hpi[j].x <= P[i].x && P[i].x <= hpi[j + 1].x)
            ans = std::min(ans, getIntersection(Line(hpi[j], hpi[j + 1] - hpi[j]), Line(t, P[i] - t)).y - P[i].y);
    }
    printf("%.3lf\n", ans);
    return 0;
}