Description

　　致力于建设全国示范和谐小村庄的H村村长dadzhi，决定在村中建立一个瞭望塔，以此加强村中的治安。我们
将H村抽象为一维的轮廓。如下图所示 我们可以用一条山的上方轮廓折线(x1, y1), (x2, y2), …. (xn, yn)来描
述H村的形状，这里x1 < x2 < …< xn。瞭望塔可以建造在[x1, xn]间的任意位置, 但必须满足从瞭望塔的顶端可
以看到H村的任意位置。可见在不同的位置建造瞭望塔，所需要建造的高度是不同的。为了节省开支，dadzhi村长
希望建造的塔高度尽可能小。请你写一个程序，帮助dadzhi村长计算塔的最小高度。
Input

　　第一行包含一个整数n，表示轮廓折线的节点数目。接下来第一行n个整数, 为x1 ~ xn. 第三行n个整数，为y1
~ yn。
Output

　　仅包含一个实数，为塔的最小高度，精确到小数点后三位。
Sample Input
【输入样例一】

6

1 2 4 5 6 7

1 2 2 4 2 1

【输入样例二】

4

10 20 49 59

0 10 10 0
Sample Output
【输出样例一】

1.000

【输出样例二】

14.500

解题方法： 我们在纸上画一画发现，这个点要想看到所有的山顶，肯定是要在相邻两个山顶连线的半平面交中。那么显然这个相对高度最小的点肯定是在半平面交的边界上，因此有如下两种情况：
1、这个点在半平面交边界上两个直线的交点处。
2、这个点在某个山顶在半平面交的边界的投影处。
求解出半平面交后分别处理这种情况的答案，取最小值，第一次写半平面交，模板抄了hzwer的。

代码如下：

//bzoj 1038 HalfplaneIntersection
//zxy
#include <bits/stdc++.h>
using namespace std;
double ans = 1e10;
int n, cnt, tot;
struct Point{
    double x, y;
    Point(){}
    Point(double x, double y) : x(x), y(y){}
}p[1005], a[1005]; //input && Intersection of Half Plane
struct L{
    Point a, b;
    double slope;
}l[1005], q[1005];
Point operator-(Point u, Point v){
    return Point(u.x - v.x, u.y - v.y);
}
double operator *(Point u, Point v){
    return (u.x*v.y - u.y*v.x);
}
inline bool operator <(L a, L b){
    if(a.slope != b.slope) return a.slope < b.slope;
    else return (a.b - a.a) * (b.b - a.a) > 0;
}
Point inter(L a, L b){ //直线求交点,定比交点
    double k1, k2, t;
    k1 = (b.b - a.a) * (a.b - a.a);
    k2 = (a.b - a.a) * (b.a - a.a);
    t = k1 / (k1 + k2);
    Point ans;
    ans.x = b.b.x + (b.a.x - b.b.x) * t;
    ans.y = b.b.y + (b.a.y - b.b.y) * t;
    return ans;
}
bool jud(L a, L b, L t){ //判断当前直线在之前直线的左边
    Point p = inter(a, b);
    return (t.b - t.a) * (p - t.a) < 0;
}
void hpi(){ //半平面交
    int L = 1, R = 0;
    tot = 0;
    for(int i = 1; i <= cnt; i++){
        if(l[i].slope != l[i-1].slope) tot++;
        l[tot] = l[i];
    }
    cnt = tot;
    q[++R] = l[1]; q[++R] = l[2];
    for(int i = 3; i <= cnt; i++){
        while(L < R && jud(q[R-1], q[R], l[i])) R--;
        while(L < R && jud(q[L+1], q[L], l[i])) L++;
        q[++R] = l[i];
    }
    while(L < R && jud(q[R-1], q[R], q[L])) R--;
    while(L < R && jud(q[L+1], q[L], q[R])) L++;
    tot = 0;
    for(int i = L; i < R; i++) a[++tot] = inter(q[i], q[i+1]);
}
void pre_init(){ //预处理
    p[0].x = p[1].x, p[0].y = 100001;
    p[n+1].x = p[n].x, p[n+1].y = 100001; //加矩形框
    for(int i = 1; i <= n; i++){
        l[++cnt].a = p[i-1], l[cnt].b = p[i];
        l[++cnt].a = p[i], l[cnt].b = p[i+1];
    }
    for(int i = 1; i <= cnt; i++){
        l[i].slope = atan2(l[i].b.y - l[i].a.y, l[i].b.x - l[i].a.x);
    }
    sort(l + 1, l + cnt + 1);
}
void work(){
    for(int k = 1; k <= tot; k++){ //半平面交的交点上的答案
        for(int i = 1; i < n; i++){
            Point t; t.x = a[k].x; t.y = -1;
            if(a[k].x >= p[i].x && a[k].x <= p[i+1].x){
                ans = min(ans, a[k].y - inter((L){p[i], p[i+1]}, (L){t, a[k]}).y);
            }
        }
    }
    for(int k = 1; k <= n; k++){ //在平面上的点
        for(int i = 1; i < tot; i++){
            Point t; t.x = p[k].x; t.y = -1;
            if(p[k].x >= a[i].x && p[k].x <= a[i+1].x){
                ans = min(ans, inter((L){a[i], a[i+1]}, (L){t, p[k]}).y - p[k].y);
            }
        }
    }
}
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);
    pre_init();
    hpi();
    work();
    printf("%.3f\n", ans);
    return 0;
}