考虑离线操作，求出每个向量存在的时间区间，用时间线段树来进行分治，在每个节点求出凸壳后，询问时在凸壳上三分答案。时间复杂度$O(n\log^2n)$。

 

#include
     
      #include
      
       typedef long long ll;const int N=200010,M=4000000;int n,m,i,op,x,y,g[524300],v[M],nxt[M],ed,t;ll ans[N];inline void read(int&a){char c;while(!(((c=getchar())>='0')&&(c<='9')));a=c-'0';while(((c=getchar())>='0')&&(c<='9'))(a*=10)+=c-'0';}struct P{int x,y;P(){}P(int _x,int _y){x=_x,y=_y;}}a[N],b[N],c[N],d[N],q[N];inline bool cmp(const P&a,const P&b){return a.x==b.x?a.y>b.y:a.x
       
        >1;  if(c<=mid)ins(x<<1,a,mid,c,d,p);  if(d>mid)ins(x<<1|1,mid+1,b,c,d,p);}inline void ask(int x){  for(int l=0,r=t;l<=r;){    int len=(r-l)/3,m1=l+len,m2=r-len;    ll s1=(ll)c[x].x*q[m1].x+(ll)c[x].y*q[m1].y,s2=(ll)c[x].x*q[m2].x+(ll)c[x].y*q[m2].y;    if(s1>s2){      r=m2-1;      if(ans[x]
        
         >1;    dfs(x<<1,a,mid),dfs(x<<1|1,mid+1,b);  }  int i,j=0;  for(i=g[x];i;i=nxt[i])d[j++]=::a[v[i]];  if(!j)return;  std::sort(d,d+j,cmp);  for(q[t=0]=d[0],i=1;i