前言:
头皮发麻。
正题:
由于半平面交的任何一个元素都可以完全看到这条直线的任何位置,而题目要求一个点能看到所有直线的位置,显然是半平面交。
所以,我紧急学了半天计算几何入门和半平面交,总算把这道题过了。
这道题,我们可以把折线上的点按从左到右两两相连,构成 \(n-1\) 条有向直线。显然瞭望塔的最顶端在所有直线的左半平面交,否则将无法看到其中部分直线的部分位置。
那我们求完半平面交,就该考虑什么时候可能成为最优方案。先把问题简化,给出两条直线 \(y_1\) 和 \(y_2\),求 \(x\) 等于几时,有 \(\min\{\left|y_1-y_2\right|\}\)。如果两条线不平行,显然时交点处最小。那如果是不相交的线段呢?就看看两条线段的端点位置,比较一下即可。
回到这道题,最优的高度显然在半平面交的下突壳上,也就转化为两条折线的 \(\min\{\left|y_1-y_2\right|\}\)。再之后,可以进一步把折线转化为许多线段的端点首尾相接,就简化为上面简单版的问题了,取所有答案的 \(min\) 即可。
注意细节!
代码:
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
using namespace std;
#define TP template<typename T>
#define TP_ template<typename T,typename ... T_>
TP void read(T &x)
{
x=0;int f=0;char ch=getchar();
for(;ch<'0'||ch>'9';ch=getchar())ch=='-'&&(f=1);
for(;ch>='0'&&ch<='9';ch=getchar())x=(x*10)+(ch^48);
double l=0.1;
if(ch=='.')
for(ch=getchar();ch>='0'&&ch<='9';ch=getchar())x=x+l*(ch^48),l/=10;
f&&(x=-x);
}
TP_ void read(T &x,T_&...y){read(x);read(y...);}
TP void write(T x){x<0&&(putchar('-'),x=-x);static int sta[35];int top=0;do{sta[++top]=x%10,x/=10;}while(x);while(top)putchar(sta[top--]^48);}
TP void writeln(const T x){write(x);puts("");}
TP void writesp(const T x){write(x);putchar(32);}
TP_ void writeln(const T x,T_ ...y){writesp(x);writeln(y...);}
using LL=long long;
constexpr double eps=1e-6;
constexpr double inf=1e18;
struct Point{double x,y;};
struct Line{Point s,e;};
Point operator +(const Point &a,const Point &b)
{
return {a.x+b.x,a.y+b.y};
}
Point operator -(const Point &a,const Point &b)
{
return {a.x-b.x,a.y-b.y};
}
Point operator *(const Point &a,const double &t)
{
return {a.x*t,a.y*t};
}
double operator *(const Point &a,const Point &b)
{
return a.x*b.y-a.y*b.x;
}
double angle(const Line &a)//arctan
{
return atan2(a.e.y-a.s.y,a.e.x-a.s.x);
}
bool cmp(const Line &a,const Line &b)//极角+左侧排序,后面若有平行直线可以直接排除
{
double A=angle(a),B=angle(b);
return fabs(A-B)>eps?A<B:(a.e-a.s)*(b.e-b.s)<0;
}
Point cross(const Line &a,const Line &b)//交点
{
Point u=a.s-b.s,v=a.e-a.s,w=b.e-b.s;
double t=u*w/(w*v);
return a.s+v*t;
}
bool right(const Line &a,const Line &b,const Line &c)
{
Point p=cross(b,c);
return (a.e-a.s)*(p-a.s)<0;//叉积
}
double get_y(const Line &a,const double &x)
{
double k=(a.e.y-a.s.y)/(a.e.x-a.s.x);
double b=a.s.y-a.s.x*k;
return k*x+b;
}
constexpr int N=3e2+5;
Point p[N];
Line a[N],b[N],q[N];
int cnt,n;
int find_line(const double &x,const int &l,const int &r,const Line c[])//找到对应x的线段
{
int L=l,R=r;
while(L<R)
{
int mid=(L+R+1)>>1;
if(cross(c[mid-1],c[mid]).x>=x)
R=mid-1;
else
L=mid;
}
return L;
}
double half_plane()
{
double ans=inf;//取最大值,double范围比long long还大,取大点没问题,最大值不需要精度
sort(a+1,a+cnt+1,cmp);
int l,r;
l=r=1;q[1]=a[1];
for(int i=2;i<=cnt;i++)
{
if(angle(a[i])-angle(a[i-1])<eps)continue;
while(l<r&&right(a[i],q[r],q[r-1]))r--;
while(l<r&&right(a[i],q[l],q[l+1]))l++;
q[++r]=a[i];
}
while(l<r-1&&right(q[l],q[r],q[r-1]))r--;//求半平面交
//这里要写为l<r-1,因为上面我把重交点的也弹出了,而这里又是无限半平面交,可能最后只剩两条直线了,最后就被弹了
for(int i=1;i<=n;i++)//枚举折线上的拐点
{
int num=find_line(p[i].x,l,r,q);
ans=min(ans,get_y(q[num],p[i].x)-p[i].y);
}
for(int i=l;i<r;i++)//枚举半平面交的下突壳的拐点
{
Point a=cross(q[i],q[i+1]);
int num=find_line(a.x,1,n,b);
ans=min(ans,a.y-get_y(b[num],a.x));
}
return ans>-eps?fabs(ans):ans;//防-0
}
int main()
{
read(n);
for(int i=1;i<=n;i++)
read(p[i].x);
for(int i=1;i<=n;i++)
read(p[i].y);
for(int i=1;i<n;i++)
a[++cnt]={p[i],p[i+1]},b[cnt]=a[cnt];
printf("%.3lf\n",half_plane());
return 0;
}