题解

仔细分析了一下，如果写个凸包+每次暴力半平面交可以得到70分，正解有点懵啊

然后用到了一个非常结论，但是大概出题人觉得江苏神仙一个个都可以手证的结论吧。。

Minkowski sum

两个凸包分别为\(A,B\)，向量为\(\vec{v}\)

\(B + \vec{v} = A\)

那么可以得到\(\vec{v} = A - B\)

也就是第一个凸包，和第二个凸包取反，这些向量的集合两两组合能达到向量的组合

求法就是，我们找到两个凸包右下角的点，取这些凸包上的边的向量，转一圈即可，具体可以看代码。。

#include 
    
     #define fi first#define se second#define pii pair
     
      #define pdi pair
      
       #define mp make_pair#define pb push_back#define enter putchar('\n')#define space putchar(' ')#define MAXN 100005#define eps 1e-8//#define ivorysiusing namespace std;typedef long long int64;typedef double db;template
       
        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
        
         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();}