[ZJOI 2008] 瞭望塔

题目大意

村子可由一条山的上方轮廓折线 (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] 间的任意位置,但必须满足从瞭望塔的顶端可以看到村子的任意位置。求塔的最小高度。

1n3001 \leqslant n \leqslant 300

x,  y1,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;
}