题面

题解

看出这是个闵可夫斯基和了然而我当初因为见到这词汇是在\(shadowice\)巨巨的\(Ynoi\)题解里所以压根没敢学……

首先您需要知道

首先如果有一个向量\(w\)使得\(w+b=a\)，也就是使\(A,B\)的凸包有交，有\(w=a-b\)，那么我们把\(B\)的横坐标和纵坐标全部取反之后，\(w\)就必定在\(A\)和\(-B\)的闵可夫斯基和里

那么只要对\(A,-B\)求一个闵可夫斯基和的凸包就行了，然后判一下输入的向量是否在这个凸包里就行了

//minamoto#include
    
     #define R register#define inf 0x3f3f3f3f#define ll long long#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)using namespace std;char buf[1<<21],*p1=buf,*p2=buf;inline char getc(){return p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<21,stdin),p1==p2)?EOF:*p1++;}int read(){    R int res,f=1;R char ch;    while((ch=getc())>'9'||ch<'0')(ch=='-')&&(f=-1);    for(res=ch-'0';(ch=getc())>='0'&&ch<='9';res=res*10+ch-'0');    return res*f;}char sr[1<<21];int K=-1;inline void Ot(){fwrite(sr,1,K+1,stdout),K=-1;}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 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
      
       0?1:0):(a-P).norm()<(b-P).norm();}void Graham(node *A,int &ta){    P=node(inf,inf),k=0;    fp(i,1,ta)if(A[i].x
       
        
         =0)--top;        st[++top]=A[i];    }    fp(i,0,top)A[i]=A[i+top+1]=st[i];    ta=top;}void merge(){    C[tc=1]=A[0]+B[0];    R int i=0,j=0;    while(i<=ta||j<=tb){        node p1=(A[i]+B[j+1])-C[tc],p2=(A[i+1]+B[j])-C[tc];        p1*p2>=0?(C[++tc]=A[i]+B[j+1],++j):(C[++tc]=A[i+1]+B[j],++i);    }//  for(;i<=ta;++i)C[++tc]=A[i]+B[j];//  for(;j<=tb;++j)C[++tc]=A[i]+B[j];    Graham(C,tc);    ta=0,tb=0,dd=0;    while(C[dd+1].x>C[dd].x)++dd;    fp(i,0,dd)A[++ta]=C[i];    while(C[dd+1].x>=C[dd].x)++dd;    ++tc;while(C[tc-1].x==C[tc].x)--tc;    fd(i,tc,dd)B[++tb]=C[i],B[tb].y=-B[tb].y;}bool in(node *A,int tot,const node &P){    if(P.x
         
          A[tot].x)return false; int k=lower_bound(A+1,A+tot+1,P)-A; if(A[k].x==P.x)return P.y>=A[k].y; return (A[k]-P)*(A[k-1]-P)<=0;}inline bool ck(const R int &x,const R int &y){return in(A,ta,node(x,y))&&in(B,tb,node(x,-y));}int main(){// freopen("testdata.in","r",stdin);// freopen("testdata.out","w",stdout); n=read(),m=read(),q=read(),ta=n,tb=m; fp(i,1,n)A[i].x=read(),A[i].y=read(); fp(i,1,m)B[i].x=-read(),B[i].y=-read(); Graham(A,ta),Graham(B,tb); merge(); while(q--)x=read(),y=read(),sr[++K]=ck(x,y)?'1':'0',sr[++K]='\n'; return Ot(),0;}