LGP4577【JSOI2018】战争

• 题解：

  • 求出$A$ 和$-B$ 的$Minkowsiki$和再$O(logn)$判断一个点是否在凸包内；
  • $Minkowsiki$的求法比较容易忘，要多多温习才可以；

•  #include<bits/stdc++.h>
  
   #define ld long long
  
   using namespace std;
  
   const int N=;
  
   int n,m,q;
  
   struct P{
  
       ld x,y;
  
       P(ld _x=,ld _y=):x(_x),y(_y){};
  
       bool operator <(const P&a)const{return x==a.x?y<a.y:x<a.x;}
  
       P operator -(const P&a)const{return P(x-a.x,y-a.y);}
  
       P operator +(const P&a)const{return P(x+a.x,y+a.y);}
  
   }p1[N],p2[N],ch[N],p[N<<],Q;
  
   ld crs(P a,P b){return a.x*b.y-a.y*b.x;}
  
   ld len(P a){return a.x*a.x+a.y*a.y;}
  
   bool cmpQ(P a,P b){return crs(a,b)>||(crs(a,b)==&&len(a)<len(b));}
  
   char gc(){
  
       static char*P1,*P2,s[];
  
       if(P1==P2)P2=(P1=s)+fread(s,,,stdin);
  
       return(P1==P2)?EOF:*P1++;
  
   }
  
   int rd(){
  
       int x=,f=;char c=gc();
  
       while(c<''||c>''){if(c=='-')f=-;c=gc();}
  
       while(c>=''&&c<=''){x=x*+c-'';c=gc();}
  
       return x*f;
  
   }
  
   void convex(P *p,int&cnt){
  
       sort(p+,p+cnt+);
  
       int top,tmp;
  
       ch[top=]=p[];
  
       for(int i=;i<=cnt;++i){
  
           while(top>&&crs(ch[top]-ch[top-],p[i]-ch[top])<=)top--;
  
           ch[++top]=p[i];
  
       }
  
       tmp=top;
  
       for(int i=cnt-;i;--i){
  
           while(top>tmp&&crs(ch[top]-ch[top-],p[i]-ch[top])<=)top--;
  
           ch[++top]=p[i];
  
       }
  
       for(int i=;i<=top;++i)p[i]=ch[i];
  
       cnt=--top;
  
   }
  
   bool check(P Q){
  
       if(crs(p[],Q)<||crs(p[n],Q)>)return false;
  
       int pos=lower_bound(p+,p+n+,Q,cmpQ)-p-;
  
       return crs(p[pos+]-p[pos],Q-p[pos])>=;
  
   }
  
   int main(){
  
       #ifndef ONLINE_JUDGE
  
       freopen("war.in","r",stdin);
  
       freopen("war.out","w",stdout);
  
       #endif
  
       n=rd();m=rd();q=rd();
  
       for(int i=;i<=n;++i)p1[i].x=rd(),p1[i].y=rd();
  
       for(int i=;i<=m;++i)p2[i].x=-rd(),p2[i].y=-rd();
  
       convex(p1,n),convex(p2,m);
  
       int cnt=,j=;
  
       p1[n+]=p1[];p2[m+]=p2[];
  
       for(int i=;i<=n;++i){
  
           p[++cnt]=p1[i]+p2[j];
  
           while(j<=m&&crs(p2[j+]-p2[j],p1[i+]-p1[i])>=)
  
           p[++cnt]=p1[i]+p2[++j];
  
       }
  
       while(j<=m)p[++cnt]=p1[]+p2[j++];
  
       n=cnt;for(int i=;i<=n;++i)p[i]=p[i]-p[];
  
       for(int i=;i<=q;++i){
  
           Q.x=rd(),Q.y=rd();
  
           printf("%d\n",check(Q-p[]));
  
       }
  
       return ;
  
   }