题意

先求出半平面交,建造塔的地方不是拐点就是半平面交点的横坐标。

code:

SRE实战,互联网时代守护先锋!让网站飞一会, 阿里云优惠促销大全。
#include<bits/stdc++.h>
using namespace std;
const int maxn=310;
const double eps=1e-8;
const double inf=1e18;
int n,tot,cnt;
double ans=inf;
struct Point
{
    double x,y;
    inline double len(){return sqrt(x*x+y*y);}
    Point operator+(const Point a)const{return (Point){x+a.x,y+a.y};}
    Point operator-(const Point a)const{return (Point){x-a.x,y-a.y};}
    Point operator*(const double k){return (Point){x*k,y*k};}
    Point operator/(const double k){return (Point){x/k,y/k};}
    double operator*(const Point a)const{return x*a.y-y*a.x;}
    double operator&(const Point a)const{return x*a.x+y*a.y;}
}p[maxn],a[maxn];
inline int dcmp(double x)
{
    if(fabs(x)<=eps)return 0;
    return x<0?-1:1;
} 
inline Point get(Point a,Point b){return b-a;}
struct Line
{
    Point p,v;double theta;
    bool operator<(const Line& a)const
    {
        return !dcmp(theta-a.theta)?dcmp(get(p,v)*get(p,a.v))<0:dcmp(theta-a.theta)<0;
    }
}line[maxn],q[maxn];
inline Point getpoint(Line l1,Line l2)
{
    Point p1=l1.p,v1=l1.v,p2=l2.p,v2=l2.v;
    v1=get(p1,v1),v2=get(p2,v2);
    Point u=get(p1,p2);
    return p2+v2*(u*v1)/(v1*v2);
}
inline bool check(Line a,Line b,Line c)
{
    Point p=getpoint(a,b);
    return dcmp(get(c.p,c.v)*get(c.p,p))<0;
}
inline void solve()
{
    p[0]=p[1];p[0].y=inf;
    p[n+1]=p[n];p[n+1].y=inf;
    for(int i=1;i<=n+1;i++)line[++tot]=(Line){p[i-1],p[i]};
    for(int i=1;i<=tot;i++)line[i].theta=atan2(line[i].v.y-line[i].p.y,line[i].v.x-line[i].p.x);
    sort(line+1,line+tot+1);
    line[0].theta=inf;
    int num=0;
    for(int i=1;i<=tot;i++)if(line[i].theta!=line[i-1].theta)line[++num]=line[i];
    tot=num;
    int l,r;
    q[l=r=1]=line[1];q[++r]=line[2];
    for(int i=3;i<=tot;i++)
    {
        while(l<r&&check(q[r-1],q[r],line[i]))r--;
        while(l<r&&check(q[l],q[l+1],line[i]))l++;
        q[++r]=line[i];
    }   
    while(l<r&&check(q[r-1],q[r],q[l]))r--;
    while(l<r&&check(q[l],q[l+1],q[r]))l++;
    for(int i=l;i<r;i++)a[++cnt]=getpoint(q[i],q[i+1]);
}
inline void getans()
{
    for(int i=1;i<=cnt;i++) 
        for(int j=1;j<n;j++)
            if(dcmp(a[i].x-p[j].x)>=0&&dcmp(a[i].x-p[j+1].x)<=0)
                ans=min(ans,a[i].y-getpoint((Line){p[j],p[j+1]},(Line){(Point){a[i].x,-1},a[i]}).y);
    for(int i=1;i<=n;i++)
        for(int j=1;j<cnt;j++)
            if(dcmp(a[j].x-p[i].x)<=0&&dcmp(a[j+1].x-p[i].x)>=0)
                ans=min(ans,getpoint((Line){a[j],a[j+1]},(Line){(Point){p[i].x,-1},p[i]}).y-p[i].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);
    solve();getans();
    printf("%.3lf",ans);
    return 0;
}