我們發現如下結論：

1.只有編號小的點才會對編號大的點產生影響

2.當當前點的y坐標大小為1~i最大的，則不會被以前的點影響

於是，維護一個斜率單調遞增的隊列

當當前點的y坐標大小為1~i最大的，則這個點的b值為i

否則，不斷刪去隊列尾部的點，直到隊尾的點y值大於現在的點，輸出隊尾的點的編號

為什麼？因為隊尾的點的y值是1~i-1的點中最後一個y值比現在點大的，我們這個點雖然被前面的點更新，但是更新它最後一個點是隊尾的點

#include
    
     #include
     
      #include
      
       #include
       
        using namespace std;int n,x[1000010],y[1000010],st[1000010],ct,mn,b[1000010];int main(){	freopen("beatall.in","r",stdin);	freopen("beatall.out","w",stdout);	scanf("%d",&n);	for(int i=1;i<=n;i++)		scanf("%d%d",&x[i],&y[i]);	mn=-2e9;	for(int i=1;i<=n;i++){		if(y[i]>=mn){			mn=y[i];			ct=0;			st[++ct]=i;			b[i]=i;		}		else{			while(ct&&((long long)(y[st[ct-1]]-y[st[ct]])*(x[st[ct]]-x[i]))<=((long long)(x[st[ct-1]]-x[st[ct]])*(y[st[ct]]-y[i])))ct--;			b[i]=st[ct];			st[++ct]=i;		}	}	for(int i=1;i<=n;i++)		printf("%d\n",b[i]);}