令 \(a\in A,b\in B\) 则移动向量 \(\omega\) 使得存在 \(b+\omega=a\)

那么 \(\omega\) 需要满足 \(\omega=a−b\)

黑科技：闵可夫斯基和

直接构造闵可夫斯基和 \(C={a+(−b)}\)

余下问题便是判断输入的移动向量是否在 \(C\) 内

可以强行使凸包的最下面为 \((0,0)\)，这样只要找到与坐标轴夹角最接近的边就好了

# include 
    
     using namespace std;typedef long long ll;const int maxn(2e5 + 5);const double eps(1e-13);const double pi(acos(-1));const double inf(1e15);struct Point2D {    double x, y;    inline Point2D(double _x = 0, double _y = 0) {        x = _x, y = _y;    }    inline Point2D operator +(Point2D ad) const {        return Point2D(x + ad.x, y + ad.y);    }    inline Point2D operator -(Point2D ad) const {        return Point2D(x - ad.x, y - ad.y);    }    inline double operator ^(Point2D ad) const { //dot        return x * ad.x + y * ad.y;    }    inline double operator *(Point2D ad) const { //cross        return x * ad.y - y * ad.x;    }    inline Point2D operator *(double ad) const {        return Point2D(x * ad, y * ad);    }    inline double Len() {        return sqrt(x * x + y * y);    }    inline double Angle() {        return atan2(y, x);    }};struct Segment2D {    Point2D x, y;    inline Segment2D(Point2D _x = Point2D(0, 0), Point2D _y = Point2D(0, 0)) {        x = _x, y = _y;    }};inline Point2D CrossPoint2D(Segment2D a, Segment2D b) {    double k1, k2, t;    k1 = (b.y - a.x) * (a.y - a.x);    k2 = (a.y - a.x) * (b.x - a.x);    t = k2 / (k1 + k2);    return b.x + (b.y - b.x) * t;}Point2D tmp[maxn];inline int Cmp(Point2D x, Point2D y) {    return (x - tmp[1]) * (y - tmp[1]) > 0;}inline void Graham(Point2D *a, int &len) {    int l = 0, mn = 0, i;    for (i = 1; i <= len; ++i)        if (!mn || (a[i].x < a[mn].x || (a[i].x == a[mn].x && a[i].y < a[mn].y))) mn = i;    swap(a[1], a[mn]), tmp[l = 1] = a[1], sort(a + 2, a + len + 1, Cmp);    for (i = 2; i <= len; ++i) {        while (l > 1 && (a[i] - tmp[l - 1]) * (tmp[l] - tmp[l - 1]) >= 0) --l;        tmp[++l] = a[i];    }    for (i = 1; i <= l; ++i) a[i] = tmp[i];    len = l;}int n, m, q, len;Point2D a[maxn], b[maxn], c[maxn], p;inline void Minkowski() {    int i, j;    c[len = 1] = a[1] + b[1], a[0] = a[1], b[0] = b[1];    for (i = 1; i < n; ++i) a[i] = a[i + 1] - a[i];    for (i = 1; i < m; ++i) b[i] = b[i + 1] - b[i];    a[n] = a[0] - a[n], b[m] = b[0] - b[m];    for (i = j = 1; i <= n || j <= m; )        if (j > m || (i <= n && a[i] * b[j] >= 0)) ++len, c[len] = c[len - 1] + a[i++];        else ++len, c[len] = c[len - 1] + b[j++];}inline int Query() {    int l, r, mid, cur = 2;    p = p - c[1];    if (c[len] * p > 0 || p * c[2] > 0) return 0;    l = 2, r = len - 1;    while (l <= r) {        mid = (l + r) >> 1;        if (c[mid] * p > 0) l = mid + 1, cur = mid;        else r = mid - 1;    }    return (p - c[cur]) * (c[cur + 1] - c[cur]) <= 0;}int main() {    int i;    scanf("%d%d%d", &n, &m, &q);    for (i = 1; i <= n; ++i) scanf("%lf%lf", &a[i].x, &a[i].y);    for (i = 1; i <= m; ++i) scanf("%lf%lf", &b[i].x, &b[i].y), b[i] = b[i] * -1;    Graham(a, n), Graham(b, m), Minkowski(), Graham(c, len);    for (i = 2; i <= len; ++i) c[i] = c[i] - c[1];    for (i = 1; i <= q; ++i) scanf("%lf%lf", &p.x, &p.y), printf("%d\n", Query());    return 0;}