题解
仔细分析了一下，如果写个凸包+每次暴力半平面交可以得到70分，正解有点懵啊
然后用到了一个非常结论，但是大概出题人觉得江苏神仙一个个都可以手证的结论吧。。
Minkowski sum
两个凸包分别为(A,B)，向量为(vec{v})
(B + vec{v} = A)
那么可以得到(vec{v} = A - B)
也就是第一个凸包，和第二个凸包取反，这些向量的集合两两组合能达到向量的组合
求法就是，我们找到两个凸包右下角的点，取这些凸包上的边的向量，转一圈即可，具体可以看代码。。
#include <bits/stdc++.h>
#define fi first
#define se second
#define pii pair<int,int>
#define pdi pair<db,int>
#define mp make_pair
#define pb push_back
#define enter putchar('
')
#define space putchar(' ')
#define MAXN 100005
#define eps 1e-8
//#define ivorysi
using namespace std;
typedef long long int64;
typedef double db;
template<class T>
void read(T &res) {
res = 0;char c = getchar();T f = 1;
while(c < '0' || c > '9') {
if(c == '-') f = -1;
c = getchar();
}
while(c >= '0' && c <= '9') {
res = res * 10 + c - '0';
c = getchar();
}
res *= f;
}
template<class T>
void out(T x) {
if(x < 0) {x = -x;putchar('-');}
if(x >= 10) {
out(x / 10);
}
putchar('0' + x % 10);
}
struct Point {
db x,y;
Point(db _x = 0.0,db _y = 0.0) {
x = _x;y = _y;
}
friend Point operator + (const Point &a,const Point &b) {
return Point(a.x + b.x,a.y + b.y);
}
friend Point operator - (const Point &a,const Point &b) {
return Point(a.x - b.x,a.y - b.y);
}
friend Point operator * (const Point &a,const db &d) {
return Point(a.x * d,a.y * d);
}
friend db operator * (const Point &a,const Point &b) {
return a.x * b.y - a.y * b.x;
}
friend db dot(const Point &a,const Point &b) {
return a.x * b.x + a.y * b.y;
}
db norm() {
return x * x + y * y;
}
}A[MAXN],B[MAXN],C[MAXN * 2],sta[MAXN * 2],S,va[MAXN],vb[MAXN];
int N,M,top,tot,Q;
bool cmp(Point a,Point b) {
db d = (a - S) * (b - S);
if(d == 0.0) {return (a - S).norm() < (b - S).norm();}
else return d > 0;
}
int Convex(int n,Point *p) {
for(int i = 2 ; i <= n ; ++i) {
if(p[i].x < p[1].x || (p[i].x == p[1].x && p[i].y < p[1].y)) swap(p[1],p[i]);
}
S = p[1];
sort(p + 2,p + n + 1,cmp);
top = 0;
for(int i = 1 ; i <= n ; ++i) {
while(top >= 2 && (p[i] - sta[top - 1]) * (sta[top] - sta[top - 1]) >= 0) --top;
sta[++top] = p[i];
}
n = top;
for(int i = 1 ; i <= n ; ++i) p[i] = sta[i];
return n;
}
void Process() {
tot = 0;
for(int i = 1 ; i < N ; ++i) {
va[i] = A[i + 1] - A[i];
}
for(int i = 1 ; i < M ; ++i) {
vb[i] = B[i + 1] - B[i];
}
va[N] = A[1] - A[N];
vb[M] = B[1] - B[M];
int al = 1,bl = 1; C[++tot] = A[1] + B[1];
while(al <= N && bl <= M) {
if(va[al] * vb[bl] >= 0) {
C[tot + 1] = C[tot] + va[al++];
}
else {
C[tot + 1] = C[tot] + vb[bl++];
}
++tot;
}
while(al <= N) {C[tot + 1] = C[tot] + va[al++];++tot;}
while(bl <= M) {C[tot + 1] = C[tot] + vb[bl++];++tot;}
}
bool Find(Point p) {
if(p * (C[2] - C[1]) > 0 || (C[tot] - C[1]) * p > 0) return false;
if(p * (C[2] - C[1]) == 0.0) {
if(p.norm() <= (C[2] - C[1]).norm()) return true;
return false;
}
int L = 2,R = tot - 1;
while(L < R) {
int mid = (L + R + 1) >> 1;
if((C[mid] - C[1]) * p > 0) L = mid;
else R = mid - 1;
}
return (C[L] - C[1]) * p + p * (C[L + 1] - C[1]) <= (C[L] - C[1]) * (C[L + 1] - C[1]);
}
void Solve() {
read(N);read(M);read(Q);
int x,y;
for(int i = 1 ; i <= N ; ++i) {
read(x);read(y);A[i] = Point(x,y);
}
for(int i = 1 ; i <= M ; ++i) {
read(x);read(y);B[i] = Point(-x,-y);
}
N = Convex(N,A);M = Convex(M,B);
Process();tot = Convex(tot,C);
Point d;
for(int i = 1 ; i <= Q ; ++i) {
read(x);read(y);
d = Point(x,y);
if(Find(d - C[1])) {puts("1");}
else puts("0");
}
}
int main() {
#ifdef ivorysi
freopen("f1.in","r",stdin);
#endif
Solve();
}