解題思路

我們需要每次求給一個凸包加上一個向量後是否與另外一個凸包相交，也就是說是否存在

$$

b\in B,(b+w)\in A

這裡 $A, B$ 表示凸包内部的點集，可以轉化一步變成

a\in A,b \in B,b+w=a \\ w =a -b

「JSOI2018」戰争

\[b\in B,(b+w)\in A

\]

這裡 \(A, B\) 表示凸包内部的點集，可以轉化一步變成

\[a\in A,b \in B,b+w=a \\ w =a -b

那相當于對 \(A,(-B)\) 作闵可夫斯基和，判斷 \(w\) 是否在新的凸包内部，把新的凸包劃分成三角區域，讓 \(w\) 和原點做一條向量，二分一下在哪個區域然後判斷一下在區域内部還是外部就可以了，複雜度 \(\mathcal O(n \log n)\) 。

code

/*program by mangoyang*/ 
#include<bits/stdc++.h>
#define inf (0x7f7f7f7f)
#define Max(a, b) ((a) > (b) ? (a) : (b))
#define Min(a, b) ((a) < (b) ? (a) : (b))
typedef long long ll;
using namespace std;
template <class T>
inline void read(T &x){
    int ch = 0, f = 0; x = 0;
    for(; !isdigit(ch); ch = getchar()) if(ch == '-') f = 1;
    for(; isdigit(ch); ch = getchar()) x = x * 10 + ch - 48;
    if(f) x = -x;
}
const int N = 1000005;
struct P{
	ll x, y;
	friend P operator + (P a, P b){ return (P){a.x + b.x, a.y + b.y}; }
	friend P operator - (P a, P b){ return (P){a.x - b.x, a.y - b.y}; }
	friend ll operator * (P a, P b){ return a.x * b.y - b.x * a.y; }
	inline ll dis(){ return x * x + y * y; }
}A[N], B[N], C[N], s1[N], s2[N], st[N], O;
int n, m, q;
inline bool cmp1 (P A, P B){ 
	return A.y != B.y ? A.y < B.y : A.x < B.x;
}
inline bool cmp2 (P A, P B){ 
	//叉積一樣按照離原點距離排，防止較遠的點被近的點日掉
	ll res = (A - O) * (B - O);
	return res ? res > 0 : (A - O).dis() < (B - O).dis();
}
inline int convex(P *A, int len){ 
	//求點集 A 的凸包并傳回凸包大小
	sort(A + 1, A + len + 1, cmp1); O = A[1];
	sort(A + 2, A + len + 1, cmp2);
	int top = 1; st[top] = A[1];
	for(int i = 2; i <= len; i++){
		while(top > 1 && (st[top] - st[top-1]) * (A[i] - st[top-1]) <= 0) top--;
		st[++top] = A[i];
	}
	for(int i = 1; i <= top; i++) A[i] = st[i];
	return top;
}
inline int inconvex(P x, P *A, int len){ 
	//判斷點 x 是否在大小為len的凸包 A 裡，二分找到向量所在的三角區域
	O = A[1];
	if((x - O) * (A[2] - O) > 0 || (x - O) * (A[len] - O) < 0) return 0;
	int pos = lower_bound(A + 2, A + len + 1, x, cmp2) - A - 1;
	return (x - A[pos]) * (A[pos%len+1] - A[pos]) <= 0;

}
inline int Minkowski(P *A, P *B, P *C, int n, int m){
	//将大小為 n, m 的凸包 A, B 的闵可夫斯基和存在 C 中，并傳回凸包大小
	int tot1 = 0, tot2 = 0;
	for(int i = 1; i < n; i++) s1[++tot1] = A[i+1] - A[i];
	s1[++tot1] = A[1] - A[n];
	for(int i = 1; i < m; i++) s2[++tot2] = B[i+1] - B[i];
	s2[++tot2] = B[1] - B[m];
	int p1 = 1, p2 = 1, tot = 1; C[tot] = A[1] + B[1];
	for(; p1 <= n && p2 <= m; tot++)
		C[tot+1] = C[tot] + (s1[p1] * s2[p2] >= 0 ? s1[p1++] : s2[p2++]);
	for(; p1 <= n; p1++, tot++) C[tot+1] = C[tot] + s1[p1];
	for(; p2 <= m; p2++, tot++) C[tot+1] = C[tot] + s2[p2];
	return tot = convex(C, tot);
}
int main(){
	read(n), read(m), read(q);
	for(int i = 1; i <= n; i++) read(A[i].x), read(A[i].y);
	n = convex(A, n);
	for(int i = 1; i <= m; i++)
		read(B[i].x), read(B[i].y), B[i].x = -B[i].x, B[i].y = -B[i].y;
	m = convex(B, m);
	int len = Minkowski(A, B, C, n, m);
	while(q--){
		ll x, y; read(x), read(y);
		printf("%d\n", inconvex((P){x, y}, C, len));
	}
	return 0;
}