链接

• 给定二元组\((a,b)\)，对于每一个\((a,b)\)询问是否存在\((A,B)\)，使得\(\frac {A}{a}+\frac {B}{b}\)在所有元素中最小，\(a,b\)实数，\(n\leq10^5\)
• 首先\(A,B\)的具体取值是没有要求的，我们只关心\(\frac {A}{B}\)。
• 化简一下，有\[z=\frac {\frac {A}{B}}{a_i}+ \frac {1}{b_i}\]
• 令\(\frac {A}{B}=x\)，有\[y=\frac {x}{a_i} + \frac {1}{b_i}\]
• 所以问题转化成，给出\(n\)条直线，询问是否存在一个\(x\)使得对应直线\(y\)取值最小。
• 维护一个下凸壳即可。
• 注意这个斜率不能直接求，精度会炸裂，要这样：
  \[k=\frac {\frac {1}{b_j}-\frac {1}{b_i}}{\frac {1}{a_i}-\frac {1}{a_j}}\]
  \[=\frac {a_i*a_j*(b_i-b_j)}{b_i*b_j*(a_j-a_i)}\]
• 这样的精度就会好一点。

#include
    
     #define R register int#define ll long long#define db long doubleusing namespace std;const int N=500001;int n,tot,len,tp,ans[N];vector
     
      G[N];struct Qs{int u,v,id;}w[N],Q[N],STK[N];int cmp(const Qs &x,const Qs &y){    if(x.u==y.u)return x.v>y.v;    return x.u
      
       '9')&&c!='-')c=getchar();    if(c=='-')k=-1,c=getchar();    while(c>='0'&&c<='9')x=(x<<3)+(x<<1)+c-'0',c=getchar();    return x*k;}db sol(Qs x,Qs y){    db fz=(db)x.u*y.u*(x.v-y.v);    db fm=(db)x.v*y.v*(y.u-x.u);    return fz/fm;}int main(){    freopen("slay.in","r",stdin);    freopen("slay.out","w",stdout);    n=gi();    for(R i=1;i<=n;++i)w[i]=(Qs){gi(),gi(),i};    sort(w+1,w+n+1,cmp);    for(R i=1,j=1;i<=n;i=j=j+1){        while(j
       
        1&&sol(STK[tp],STK[tp-1])>sol(Q[i],STK[tp-1]))--tp;        STK[++tp]=Q[i];    }    for (R i=1;i<=tp;++i)        if (i==tp||sol(STK[i],STK[i+1])>0){            R x=STK[i].id;            for(R i=0,sz=G[x].size();i