题面

题解

题目转化一下就是所有点都在直线\(Ax+By-C=0\)的同一侧，也就可以看做所有点代入\(Ax+By-C\)之后的值符号相同，我们只要维护每一个点代入直线之后的最大值和最小值，看看每条直线的最大最小值符号是否相同就好了

以最大值为例，我们强制\(B\geq 0\)，那么能令这条直线取到最大值的点一定在所有点的上凸壳上，我们把凸壳搞出来，然后把所有直线按斜率从小到大排序，一遍扫过去就可以更新答案了

然而对于每条直线把前面所有点做个凸包？那有个吉儿用我还不如暴力枚举来得快

我们考虑\(CDQ\)分治，每次把\([l,mid]\)之间的点做一个凸包，然后用来更新\([mid+1,r]\)之间的答案就行了

//minamoto#include
    
     #define R register#define ll long long#define inf 1e18#define fp(i,a,b) for(R int i=(a),I=(b)+1;i
     
      I;--i)#define go(u) for(int i=head[u],v=e[i].v;i;i=e[i].nx,v=e[i].v)template
      
       inline bool cmin(T&a,const T&b){return a>b?a=b,1:0;}template
       
        inline bool cmax(T&a,const T&b){return a
        
         '9'||ch<'0')(ch=='-')&&(f=-1);    for(res=ch-'0';(ch=getc())>='0'&&ch<='9';res=res*10+ch-'0');    return res*f;}const int N=2e5+5;struct node{    int x,y;    node(){}    node(R int xx,R int yy):x(xx),y(yy){}    inline node operator -(const node &b)const{return node(x-b.x,y-b.y);}    inline ll operator *(const node &b)const{return 1ll*x*b.y-1ll*y*b.x;}    inline bool operator <(const node &b)const{return x==b.x?y
         
          
           =0;}inline bool cmp2(const query &x,const query &y){return x.p*y.p<=0;}int ans[N];ll mn[N],mx[N],vc[N],maxn,minn;int op[N],n,m,tot,top,cnt,t;inline void upd(R int id,R int x,R int y){// printf("%d %d %d\n",id,x,y); R ll val=las[id].a*x+las[id].b*y-las[id].c; cmax(mx[id],val),cmin(mn[id],val);}void solve(int l,int r){ if(l==r)return; int mid=(l+r)>>1; solve(l,mid),solve(mid+1,r),top=cnt=tot=0; fp(i,l,mid)if(q[i].op&1)p[++tot]=node(q[i].a,q[i].b); fp(i,mid+1,r)if(q[i].op&2)c[++cnt]=query(q[i].a,q[i].b,q[i].c,node(q[i].b,-q[i].a),q[i].id); if(!tot||!cnt)return; sort(p+1,p+1+tot),st[top=1]=p[1]; fp(i,2,tot){ while(top>1&&(p[i]-st[top-1])*(st[top]-st[top-1])>=0)--top; st[++top]=p[i]; } sort(c+1,c+1+cnt,cmp1);// printf("%d %d %d\n",l,r,cnt);// fp(i,1,cnt)printf("%d\n",c[i].id); for(R int i=1,j=1;i<=top;++i){ while(j<=cnt&&(i+1>top||(c[j].p*(st[i+1]-st[i]))>=0)) upd(c[j].id,st[i].x,st[i].y),++j; } st[top=1]=p[1]; fp(i,2,tot){ while(top>1&&(p[i]-st[top-1])*(st[top]-st[top-1])<=0)--top; st[++top]=p[i]; } sort(c+1,c+1+cnt,cmp2); for(R int i=1,j=1;i<=top;++i){ while(j<=cnt&&(i+1>top||c[j].p*(st[i+1]-st[i])<=0)) upd(c[j].id,st[i].x,st[i].y),++j; }}int main(){// freopen("testdata.in","r",stdin); n=read(),m=read(),maxn=-inf,minn=inf; fp(i,1,n)q[i].op=1,q[i].a=read(),q[i].b=read(),cmax(maxn,q[i].a),cmin(minn,q[i].a); t=n; fp(i,1,m)ans[i]=-1; fp(i,1,m){ ++t,op[i]=q[t].op=read(); if(q[t].op&1)q[t].a=read(),q[t].b=read(),cmax(maxn,q[t].a),cmin(minn,q[t].a); else{ q[t].a=read(),q[t].b=read(),q[t].c=read(); if(!q[t].b)ans[i]=(-1.0*q[t].c/q[t].a
           
            maxn),--t; else{ if(q[t].b<0)q[t].a=-q[t].a,q[t].b=-q[t].b,q[t].c=-q[t].c; mn[i]=inf,mx[i]=-inf,q[t].id=i; las[i].a=q[t].a,las[i].b=q[t].b,las[i].c=q[t].c; } } }// fp(i,1,t)printf("%d %d %lld %lld %lld\n",q[i].op,q[i].id,q[i].a,q[i].b,q[i].c); solve(1,t); fp(i,1,t)if(q[i].op&2)ans[q[i].id]=(mx[q[i].id]<0||mn[q[i].id]>0); fp(i,1,m)if(op[i]&2)puts(ans[i]?"YES":"NO"); return 0;}