这是一道非常有意思的题目
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
1 2 4 5 6 7
1 2 2 4 2 1
【输入样例二】
4
10 20 49 59
0 10 10 0
10 20 49 59
0 10 10 0
Sample Output
【输出样例一】
1.000
【输出样例二】
14.500
1.000
【输出样例二】
14.500
HINT
N ≤ 300，输入坐标绝对值不超过106，注意考虑实数误差带来的问题。
题解
经过研究，我们发现能看见一段山坡的是一个半平面
于是半平面交
我们得到了一个上凸壳和一段折线，求这两个玩意水平的最短距离
这个嘛，我们发现一定是在上凸壳或者折线的顶点处最小
然后明显一个点对应的一段线是单调的。
问题解决
虽然这题只有300
但是这个能做300000
#include<stdio.h>
#include<stdlib.h>
#include<iostream>
#include<string>
#include<string.h>
#include<algorithm>
#include<math.h>
#include<queue>
#include<map>
#include<vector>
#include<set>
#define il inline
#define re register
#define linf 1e15
using namespace std;
const int N=;
typedef double db;
int n,m,L,R,p;
db ans=1e60;
struct P{db x,y;} a[N],c[N],t,tt;
struct line{P a,b;db slop;} l[N],q[N];
il P operator-(P a,P b){
return (P){a.x-b.x,a.y-b.y};
}
il db operator*(P a,P b){
return a.x*b.y-a.y*b.x;
}
il bool cmp(line a,line b){
if(a.slop!=b.slop) return a.slop<b.slop;
return (a.b-a.a)*(b.b-a.a)>;
}
il P inter(line a,line 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);P 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;
}
il bool jud(line a,line b,line t){
P p=inter(a,b);
return (p-t.a)*(t.b-t.a)>;
}
il void print(P a){
printf("(%lf,%lf)\n",a.x,a.y);
}
int main(){
scanf("%d",&n);m=n-;
for(int i=;i<=n;i++) scanf("%lf",&a[i].x);
for(int i=;i<=n;i++) scanf("%lf",&a[i].y);
for(int i=;i<n;i++){
l[i].a=a[i];
l[i].b=a[i+];
}
l[++m]=(line){(P){a[].x,1e7},a[]};
l[++m]=(line){a[n],(P){a[n].x,1e7}};
for(int i=;i<=m;i++)
l[i].slop=atan2(l[i].b.y-l[i].a.y,l[i].b.x-l[i].a.x);
sort(l+,l+m+,cmp);
L=;R=;
q[]=l[];q[]=l[];
for(int i=;i<=m;i++){
while(L<R&&jud(q[R-],q[R],l[i])) R--;
while(L<R&&jud(q[L],q[L+],l[i])) L++;
q[++R]=l[i];
}
while(L<R&&jud(q[R-],q[R],q[L])) R--;
while(L<R&&jud(q[L],q[L+],q[R])) L++;
for(int i=L;i<R;i++)
c[++p]=inter(q[i],q[i+]);
for(int i=,j=;i<=n;i++){
while(j<p&&(!(c[j].x<=a[i].x&&a[i].x<=c[j+].x))) j++;
if(j<p){
tt=(P){a[i].x,-};
t=inter((line){tt,a[i]},(line){c[j],c[j+]});
ans=min(ans,t.y-a[i].y);
}
}
for(int i=,j=;i<=p;i++){
while(j<n&&(!(a[j].x<=c[i].x&&c[i].x<=a[j+].x))) j++;
if(j<n){
tt=(P){c[i].x,-};
t=inter((line){tt,c[i]},(line){a[j],a[j+]});
ans=min(ans,c[i].y-t.y);
}
}
printf("%.3lf",ans);
return ;
}