这个是题目描述：

题解：

啊啊啊啊啊……

垃圾分数规划。

垃圾树链剖分。

垃圾斜率优化。

垃圾darkbzoj。

这里才是题解：

我们设那个分数的值=k，那么有

$(yi-k*xi)+(qj-k*pj)=0$

我们要做的是让k最大。

那么很明显开两颗线段树，每个节点存一个凸包。

鉴于我们要让b值最大，我们要维护一个上凸包。

然后就是三分凸包+树剖。

代码：

#include
      
       #include
       
        #include
        
         #include
         
          #include
          
           using namespace std;#define N 30050#define db doubleint n,hed[N],cnt,m;const db inf = 1e10;const db eps = 1e-6;struct Pnt{    db x,y;}p1[N],p2[N];struct EG{    int to,nxt;}e[2*N];void ae(int f,int t){    e[++cnt].to = t;    e[cnt].nxt = hed[f];    hed[f] = cnt;}int fa[N],siz[N],son[N],dep[N],top[N];int tin[N],tim;void dfs1(int u,int f){    siz[u]=1;    fa[u]=f;    dep[u]=dep[f]+1;    for(int j=hed[u];j;j=e[j].nxt)    {        int to = e[j].to;        if(to==f)continue;        dfs1(to,u);        siz[u]+=siz[to];        if(siz[to]>siz[son[u]])son[u]=to;    }}void dfs2(int u,int tp){    top[u]=tp;    tin[u]=++tim;    if(son[u])    {        dfs2(son[u],tp);        for(int j=hed[u];j;j=e[j].nxt)        {            int to = e[j].to;            if(to==fa[u]||to==son[u])continue;            dfs2(to,to);        }    }}struct Pair{    db x,y;int id;    Pair(){}    Pair(db x,db y,int i):x(x),y(y),id(i){}    friend bool operator < (Pair a,Pair b)    {        if(fabs(a.x-b.x)
           
            =2&&(tmp[i].y-y[s[ct]])*(x[s[ct]]-x[s[ct-1]])>(y[s[ct]]-y[s[ct-1]])*(tmp[i].x-x[s[ct]])) ct--; s[++ct]=tmp[i].id; } beg[u]=tm+1; for(int i=1;i<=ct;i++)a[++tm]=s[i]; ens[u]=tm; if(l==r)return ; int mid = (l+r)>>1; build(l,mid,u<<1); build(mid+1,r,u<<1|1); } int ret; void div_3(int u,db k) { int l = beg[u],r = ens[u]; while(r-l>3) { int lm = (l+l+r)/3,rm = (l+r+r)/3; if(y[a[lm]]-k*x[a[lm]]>y[a[rm]]-k*x[a[rm]])r=rm; else l=lm; } for(int i=l;i<=r;i++) if(y[a[i]]-k*x[a[i]]>y[ret]-k*x[ret])ret=a[i]; } void query(int l,int r,int u,int ql,int qr,db k) { if(l==ql&&r==qr) { div_3(u,k); return ; } int mid = (l+r)>>1; if(qr<=mid)query(l,mid,u<<1,ql,qr,k); else if(ql>mid)query(mid+1,r,u<<1|1,ql,qr,k); else query(l,mid,u<<1,ql,mid,k),query(mid+1,r,u<<1|1,mid+1,qr,k); } int get_ret(int x,int y,db k) { ret = tin[x]; while(top[x]!=top[y]) { if(dep[top[x]]
            
             dep[y])swap(x,y); query(1,n,1,tin[x],tin[y],k); return ret; }}tr[2];db gt(int x,int y,db k){ int a = tr[0].get_ret(x,y,k); int b = tr[1].get_ret(x,y,k); return (tr[0].y[a]+tr[1].y[b])/(tr[0].x[a]+tr[1].x[b]);}int main(){ scanf("%d",&n); for(int i=1;i<=n;i++)scanf("%lf",&p1[i].x); for(int i=1;i<=n;i++)scanf("%lf",&p1[i].y); for(int i=1;i<=n;i++)scanf("%lf",&p2[i].x); for(int i=1;i<=n;i++)scanf("%lf",&p2[i].y); for(int f,t,i=1;i
             
              1e-4) { las = ans; ans = gt(x,y,las); } printf("%.4lf\n",ans); } return 0;}