Description：

给出平面上两组点 $A$ 和 $B$ ，任意两点不重合，多次询问，每次给出一个向量，求把点集 $B$ 中的所有点按照这个向量移动后 $A$ 和 $B$ 的凸包是否有交。

$1\leqslant n\leqslant 5\times 10^5$

Solution：

前置知识：点集 $A=\{(x_i,y_i)\},B=\{(x_i,y_i)\}$ 的闵科夫斯基和为 $C=\{(x_a+x_b,y_x+y_b)|(x_a,y_a)\in A,(x_b,y_b)\in B\}$

定义 $S_A=convex(A)$ 为点集 $A$ 的凸包，那么询问也就是要判断是否存在 $p_a\in S_A,p_b\in S_B$ 满足 $p_a=p_b+\overrightarrow v$ ，移项，得： $\overrightarrow v=p_a-p_b$ ，那么问题就转变成了 $\overrightarrow v$ 在不在 $A$ 和 $-B$ 的闵科夫斯基和中，于是就可以做了。

还需要用一个 $O(\log n)$ 判断点在凸包里的科技。

Code：

#include<algorithm>

#include<iostream>

#include<cstdlib>

#include<cstdio>

#include<cmath>

#include<cctype>

#include<cstring>

using namespace std;

inline int rd()

{

	register int res = 0,f = 1;register char c = getchar();

	while(!isdigit(c)){if(c == '-')f = -1;c = getchar();}

	while(isdigit(c))res = (res << 1) + (res << 3) + c - '0',c = getchar();

	return res * f;

}

int n,m,q;

#define MAXN 200010

struct point

{

	int x,y;

}pn[MAXN],pm[MAXN];

point operator + (point a,point b){return (point){a.x + b.x,a.y + b.y};}

point operator - (point a,point b){return (point){a.x - b.x,a.y - b.y};}

typedef long long ll;

ll operator * (point a,point b){return 1ll * a.x * b.y - 1ll * a.y * b.x;}

bool operator == (point a,point b){return a.x == b.x && a.y == b.y;}

point cn[MAXN],cm[MAXN];

point st1[MAXN],st2[MAXN];

int tp1 = 0,tp2 = 0;

point p1[MAXN],p2[MAXN];

int cnt1 = 0,cnt2 = 0;

double slope(point a,point b){return 1.0 * (a.y - b.y) / (a.x - b.x);}

bool operator < (point a,point b){return (a.x == b.x ? a.y < b.y : a.x < b.x);}

int getconvex(point p[],point c[],int n)

{

	cnt1 = cnt2 = tp1 = tp2 = 0;

	sort(p + 1,p + 1 + n);

	for(int i = 1;i <= n;++i)

	{

		if(cnt1 == 0 || p[i].x != p1[cnt1].x)p1[++cnt1] = p[i];

		else if(p[i].y >= p1[cnt1].y)p1[cnt1] = p[i];

	}

	for(int i = 1;i <= n;++i)

	{

		if(cnt2 == 0 || p[i].x != p2[cnt2].x)p2[++cnt2] = p[i];

		else if(p[i].y <= p2[cnt2].y)p2[cnt2] = p[i];

	}

	for(int i = 1;i <= cnt1;++i)

	{

		while(tp1 >= 2 && slope(st1[tp1 - 1],st1[tp1]) <= slope(st1[tp1],p1[i]))--tp1;

		st1[++tp1] = p1[i];

	}

	for(int i = 1;i <= cnt2;++i)

	{

		while(tp2 >= 2 && slope(st2[tp2 - 1],st2[tp2]) >= slope(st2[tp2],p2[i]))--tp2;

		st2[++tp2] = p2[i];

	}

	int tot = 0;

	for(int i = 1;i <= tp2;++i)c[++tot] = st2[i];

	if(!(st1[tp1] == st2[tp2]))c[++tot] = st1[tp1];

	for(int i = tp1 - 1;i >= 2;--i)c[++tot] = st1[i];

	if(!(st1[1] == st2[1]))c[++tot] = st1[1];

	return tot;

}

point s[MAXN];

int sum;

int merge(point cn[],int n,point cm[],int m,point s[])

{

	for(int i = 1;i < n;++i)st1[i] = cn[i + 1] - cn[i];st1[n] = cn[1] - cn[n];

	for(int i = 1;i < m;++i)st2[i] = cm[i + 1] - cm[i];st2[m] = cm[1] - cm[m];

	int tot = 0;

	s[tot = 1] = cn[1] + cm[1];

	int p1 = 1,p2 = 1;

	while(p1 <= n && p2 <= m)++tot,s[tot] = s[tot - 1] + (st1[p1] * st2[p2] >= 0 ? st1[p1++] : st2[p2++]);

	while(p1 <= n)++tot,s[tot] = s[tot - 1] + st1[p1++];

	while(p2 <= m)++tot,s[tot] = s[tot - 1] + st2[p2++];

	return tot;

}

ll len(point a){return 1ll * a.x * a.x + 1ll * a.y * a.y;}

bool cmp2(point a,point b){return a * b > 0 || (a * b == 0 && len(a) < len(b));}

bool in(point k)

{

	if(k * s[1] > 0 || s[sum] * k > 0)return 0;

	int pos = lower_bound(s + 1,s + 1 + sum,k,cmp2) - s - 1;

	return (k - s[pos]) * (s[pos % sum + 1] - s[pos]) <= 0;

}

int main()

{

	scanf("%d%d%d",&n,&m,&q);

	for(int i = 1;i <= n;++i)pn[i].x = rd(),pn[i].y = rd();

	for(int i = 1;i <= m;++i)pm[i].x = -rd(),pm[i].y = -rd();

	n = getconvex(pn,cn,n);m = getconvex(pm,cm,m);

	sum = merge(cn,n,cm,m,s);

	sum = getconvex(s,s,sum);

	point base = s[1];

	for(int i = sum;i >= 1;--i)s[i] = s[i] - s[1];

	point p;

	for(int i = 1;i <= q;++i)

	{

		scanf("%d%d",&p.x,&p.y);

		printf("%d\n",in(p - base));

	}

	return 0;

}