「BZOJ1038」[ZJOI2008]瞭望塔

Description

致力于建设全国示范和谐小村庄的H村村长dadzhi,决定在村中建立一个瞭望塔,以此加强村中的治安。
我们将HH村抽象为一维的轮廓。如下图所示

我们可以用一条山的上方轮廓折线(x1,y1),(x2,y2),,(xn,yn)(x_1, y_1), (x_2, y_2),\cdots , (x_n, y_n)来描述HH村的形状,这里x1<x2<<xnx_1 < x_2 < \cdots < x_n。瞭望塔可以建造在[x1,xn][x_1, x_n]间的任意位置, 但必须满足从瞭望塔的顶端可以看到HH村的任意位置。可见在不同的位置建造瞭望塔,所需要建造的高度是不同的。为了节省开支,dadzhi村长希望建造的塔高度尽可能小。

请你写一个程序,帮助dadzhi村长计算塔的最小高度。

Input

第一行包含一个整数nn,表示轮廓折线的节点数目。
接下来第一行nn个整数, 为x1x_1 ~ xnx_n.
第三行nn个整数,为y1y_1 ~ yny_n

Output

仅包含一个实数,为塔的最小高度,精确到小数点后三位。

Sample Input

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

Sample Output

1
1.000

HINT

对于60%60\%的数据, N60N \leq 60
对于100%100\%的数据, ¥N \leq 300$,输入坐标绝对值不超过10610^6,注意考虑实数误差带来的问题。

Solution

瞭望塔的顶点一定是在每两个相邻点构成的有向线段集合的半平面交上。
然后求每个点到半平面交的垂直距离最小值。

注意初始的时候要加一条xx轴进来,否则只有90pts90pts

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
#include<cstdio>
#include<algorithm>
#include<iostream>
#include<cstring>
#include<map>
#include<queue>
#include<cmath>
#include<bitset>
#define mk make_pair
#define fi first
#define nd second
#define pii pair<int,int>
#define pb push_back
#define sqr(x) ((x)*(x))
using namespace std;
typedef long long ll;
inline ll read() {ll x = 0; char ch = getchar(), w = 1;while(ch < '0' || ch > '9') {if(ch == '-') w = -1;
ch = getchar();}while(ch >= '0' && ch <= '9') {x = x * 10 + ch - '0';ch = getchar();}return x * w;}
void write(ll x) {if(x < 0) putchar('-'), x = -x;if(x > 9) write(x / 10);putchar(x % 10 + '0');}
inline void writeln(ll x) {write(x);puts("");}

const int N = 310;
int n;
typedef struct Vec {
double x,y;
Vec() {}
Vec(double _x, double _y) {x = _x, y = _y;}
Vec operator *(double k) {return Vec(x * k, y * k);}
Vec operator /(double k) {return Vec(x / k, y / k);}
}Pt;
Vec operator + (Vec a, Vec b) {return Vec(a.x + b.x, a.y + b.y);}
Vec operator - (Vec a, Vec b) {return Vec(a.x - b.x, a.y - b.y);}
double dot(Vec a, Vec b) {return a.x * b.x + a.y* b.y;}
double cross(Vec a, Vec b) {return a.x * b.y - a.y* b.x;}
struct Line {
Vec s, e;
Line() {}
Line(Vec _x, Vec _y) {s = _x, e = _y;}
};
Line a[N];
Pt b[N];
#define eps 1e-9
double getAtan(Line a) {
return atan2(a.e.y- a.s.y, a.e.x- a.s.x);
}
bool cmp(Line a, Line b) {
double v1 = getAtan(a);
double v2 = getAtan(b);
if(fabs(v1 - v2) < eps) return cross(a.e - a.s, b.s - a.s) < eps;
return v1 - v2 < -eps;
}
Pt getins(Line a, Line b) {
double s1 = cross(b.s - a.e, b.e - a.e);
double s2 = cross(b.e - a.s, b.s - a.s);
return a.s + (a.e - a.s) * s2 / (s1 + s2);
}
bool onR(Line a, Line b, Line c) {
Pt t = getins(b, c);
return cross(a.e - a.s, t - a.s) < -eps;
}
int h, t, q[N];
Pt u[N];
double solve() {
a[n++] = Line(Vec(0, 0), Vec(1e99, 0));
sort(a, a + n, cmp);
int c = 0;
for(int i = 0; i < n; ++i)
if(i == 0 || fabs(getAtan(a[i]) - getAtan(a[i - 1])) > eps) a[c++] = a[i];
h = 1, t = 0;
for(int i = 0; i < c; ++i) {
while(h < t && onR(a[i], a[q[t - 1]], a[q[t]])) --t;
while(h < t && onR(a[i], a[q[h]], a[q[h + 1]])) ++h;
q[++t] = i;
}
while(h < t && onR(a[q[t]], a[q[h]],a[q[h + 1]])) --t;
while(h < t && onR(a[q[h]], a[q[t - 1]], a[q[t]])) ++h;
c = 0;
for(int i = h; i < t; ++i) {
u[c++] = getins(a[q[i]], a[q[i + 1]]);
}
double ans = 1e100;
for(int i = 0; i < c; ++i) {
for(int j = 0; j < n - 1; ++j) if(u[i].x >= b[j].x&& u[i].x <= b[j + 1].x){
Pt tmp = getins(Line(b[j], b[j + 1]), Line(Pt(u[i].x, 0), u[i]));
ans = min(ans, max(0.0, u[i].y - tmp.y));
}
}
for(int i = 0; i < n; ++i) for(int j = 0; j < c - 1; ++j) if(b[i].x >= u[j].x && b[i].x <= u[j +1].x) {
Pt tmp = getins(Line(u[j], u[j + 1]), Line(Pt(b[i].x, 0), b[i]));
ans = min(ans, max(0.0, tmp.y - b[i].y));
}
return ans;
}
int main() {
n = read();
for(int i = 0; i < n; ++i)
scanf("%lf",&b[i].x);
for(int i = 0; i < n; ++i)
scanf("%lf",&b[i].y);
--n;
for(int i = 0; i < n; ++i) {
a[i] = Line(b[i], b[i + 1]);
}
printf("%.3lf\n", solve());
return 0;
}