Luogu

LOJ

分析

设第一个部落的领地为 $A$，第二个部落的领地为 $B$。

假设 $B$ 移动了 $\vec{v}$ 后 $A$ 和 $B$ 仍有交，说明存在 $a\in A,b\in B$，满足 $b+\vec{v}=a$ 即 $\vec{v}=a-b$。

构造 $A$ 和 $-B$ 的闵可夫斯基和 $C$，问题变为判断 $\vec{v}$ 是否在 $C$ 内，二分出极角相邻的点再利用叉积判断即可。

代码

// ===================================
//   author: M_sea
//   website: http://m-sea-blog.com/
// ===================================
#include <bits/stdc++.h>
#define re register
using namespace std;
typedef long long ll;

inline int read() {
    int X=0,w=1; char c=getchar();
    while (c<'0'||c>'9') { if (c=='-') w=-1; c=getchar(); }
    while (c>='0'&&c<='9') X=X*10+c-'0',c=getchar();
    return X*w;
}

const int N=100000+10;

struct Point { ll x,y; double ang; };
typedef Point Vector;
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}; }
Point operator *(Point a,ll b) { return (Point){a.x*b,a.y*b}; }
inline ll cross(Point a,Point b) { return a.x*b.y-a.y*b.x; }
inline ll dot(Point a,Point b) { return a.x*b.x+a.y*b.y; }
inline ll len2(Point a) { return a.x*a.x+a.y*a.y; }

int n,m,Q;
Point A[N],B[N];

Point s[N]; int top;
inline int cmp(Point a,Point b) {
    return a.ang!=b.ang?a.ang<b.ang:a.x<b.x;
}
inline void Graham(Point* p,int n) {
    int pos=1;
    for (re int i=2;i<=n;++i)
        if (p[i].x<p[pos].x||(p[i].x==p[pos].x&&p[i].y<p[pos].y)) pos=i;
    swap(p[pos],p[1]);
    for (re int i=2;i<=n;++i) p[i].ang=atan2(p[i].y-p[1].y,p[i].x-p[1].x);
    sort(p+2,p+n+1,cmp);
    s[top=1]=p[1];
    for (re int i=2;i<=n;++i) {
        while (top>1&&cross(s[top]-s[top-1],p[i]-s[top])<=0) --top;
        s[++top]=p[i];
    }
}

Point t1[N],t2[N],S[N]; int cnt;
inline void Minkowski(Point* A,Point* B,int n,int m) {
    A[n+1]=A[1],B[m+1]=B[1];
    for (re int i=1;i<=n;++i) t1[i]=A[i+1]-A[i];
    for (re int i=1;i<=m;++i) t2[i]=B[i+1]-B[i];
    S[cnt=1]=A[1]+B[1]; int i=1,j=1;
    while (i<=n&&j<=m) { ++cnt;
        if (cross(t1[i],t2[j])>=0) S[cnt]=S[cnt-1]+t1[i++];
        else S[cnt]=S[cnt-1]+t2[j++];
    }
    while (i<=n) ++cnt,S[cnt]=S[cnt-1]+t1[i++];
    while (j<=m) ++cnt,S[cnt]=S[cnt-1]+t2[j++];
}

inline int cmp2(Point a,Point b) {
    return cross(a,b)>0||(cross(a,b)==0&&len2(a)<len2(b));
}
inline int inside(Point x) {
    if (cross(x,S[1])>0||cross(S[cnt],x)>0) return 0;
    int p=lower_bound(S+1,S+cnt+1,x,cmp2)-S-1;
    return cross(x-S[p],S[p%cnt+1]-S[p])<=0;
}

int main() {
    n=read(),m=read(),Q=read();
    for (re int i=1;i<=n;++i) A[i].x=read(),A[i].y=read();
    Graham(A,n); n=top; for (re int i=1;i<=top;++i) A[i]=s[i];
    for (re int i=1;i<=m;++i) B[i].x=-read(),B[i].y=-read();
    Graham(B,m); m=top; for (re int i=1;i<=top;++i) B[i]=s[i];
    Minkowski(A,B,n,m);
    Graham(S,cnt); cnt=top; for (re int i=1;i<=top;++i) S[i]=s[i];
    Point O=S[1]; for (re int i=1;i<=cnt;++i) S[i]=S[i]-O;
    while (Q--) {
        int x=read(),y=read();
        printf("%d\n",inside((Point){x,y}-O));
    }
    return 0;
}