自闭了一上午。
sro Creed orz
sro suncongbo orz
真的无敌
首先，在做这个题之前，先来介绍闵可夫斯基和的相关知识，
m
i
n
k
o
w
s
k
i
s
u
m
minkowski\ sum
m
i
n
k
o
w
s
k
i
s
u
m
是两个欧几里得空间的点集的和。
假设我们定义两个点集
A
A
A
和
B
B
B
的闵可夫斯基和表示为点集
C
(
a
+
b
∣
a
∈
A
,
b
∈
B
）
C(a+b\ | a\in A,b\in B）
C
(
a
+
b
∣
a
∈
A
,
b
∈
B
）
其实就是点集中的点两两做和，然后构成一个新的点集。
这里我们讨论凸包的闵可夫斯基和
一个比较显然的性质就是，两个凸包的闵可夫斯基和还是一个凸包
搬了一个网上的图。
暴力的复杂度是
O
(
n
2
)
O(n^2)
O
(
n
2
)
的，我们考虑怎么优化这个东西。
一般的做法都是这样的，我们观察上图，不难发现，可以直接把原来两个凸包上的所有的向量，按照逆时针方向全部拎出来，然后按照极角（从x的正半轴开始的极角）排序，顺次加入即可。
这样复杂度是
O
(
n
l
o
g
n
)
O(nlogn)
O
(
n
l
o
g
n
)
的
bool cmp1(Point a,Point b)
{
int x = get(a),y=get(b);
if (x!=y) return x>y;
if(chacheng(a,b)>=0) return 1;
else return 0;
}
void minkowski()
{
lyf[1]=x[1]+y[1];
cnt=1;
sort(l+1,l+1+tmp,cmp1);
for (int i=1;i<=tmp;i++) ++cnt,lyf[cnt]=lyf[cnt-1]+l[i];
cnt--;
ymh=lyf[1];
}
这里这个
c
m
p
cmp
c
m
p
函数还是要注意一下的，因为对于
y
y
y
的正负不同的，要优先是正的。
那么现在我们该如何判断一个点是不是在凸包内部呢？
这时候考虑二分，找到这个点对应的极角最近的两个点，然后判断这个点和那两个点的向量之间的位置关系，如果是在
l
y
f
[
p
o
s
]
→
l
y
f
[
p
o
s
+
1
]
lyf[pos]\rightarrow lyf[pos+1]
l
y
f
[
p
o
s
]
→
l
y
f
[
p
o
s
+
1
]
左边，那么就是合法，否则就是不合法
还需要特判一下这个点是不是在最左下角的点的左下的位置，如果是在左下，还是不合法的。
bool erf(Point nyd)
{
if (chacheng(lyf[cnt]-lyf[1],nyd-lyf[1])>0 || chacheng(lyf[2]-lyf[1],nyd-lyf[1])<0) return 0;
int l=1,r=cnt;
int pos=0;
while (l<=r)
{
int mid = l+r >> 1;
if (chacheng(lyf[mid]-ymh,nyd-ymh)>0 || (chacheng(lyf[mid]-ymh,nyd-ymh)==0 && dis(lyf[mid],ymh)<=dis(nyd,ymh))) pos=mid,l=mid+1;
else r=mid-1;
}
// cout<<pos<<endl;
if (chacheng(lyf[pos+1]-lyf[pos],nyd-lyf[pos])>=0) return 1;
else return 0;
}
那么回到这个题
我们发现，把题目转化之后，实际上就是对于每一个询问，求将点集
b
b
b
平移
(
d
x
,
d
y
)
(dx,dy)
(
d
x
,
d
y
)
这个向量之后，是否和点集
a
a
a
是有交的。
首先，不难发现，如果存在交点，那么一定是和凸包上的点有关系的，就可以忽略内部的点，我们不妨先对于两个点集求一个凸包。
那我们令
p
p
p
表示
(
d
x
,
d
y
)
(dx,dy)
(
d
x
,
d
y
)
那么如果存在交点，那么存在一个点满足
b
+
p
=
a
b+p=a
b
+
p
=
a
p
=
a
+
(
−
b
)
p=a+(-b)
p
=
a
+
(
−
b
)
可以看出，这是一个闵可夫斯基和的形式，那么我们对于
A
A
A
和
B
B
B
（所有点的横纵坐标都取负）求一个闵可夫斯基和，然后看一看这个
p
p
p
是否是在新形成的凸包里面，如果在，说明至少存在一个交点。即可，总的来说细节真的很多。
qwq
包括闵可夫斯基和的起始点和排序之类的过程。
直接给代码
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<cmath>
#include<queue>
#include<map>
#include<set>
#define mk make_pair
#define ll long long
#define int long long
using namespace std;
inline int read()
{
int x=0,f=1;char ch=getchar();
while (!isdigit(ch)) {if (ch=='-') f=-1;ch=getchar();}
while (isdigit(ch)) {x=(x<<1)+(x<<3)+ch-'0';ch=getchar();}
return x*f;
}
const int maxn = 4e5+1e2;
const int inf = 1e9;
struct Point{
int x,y;
};
struct Line
{
Point x,y;
};
Point a[maxn],b[maxn];
int n,m,q;
int numx,numy;
Point ymh;
Point st[maxn];
Point x[maxn],y[maxn];
Point lyf[maxn];
Point l[maxn];
int tmp1;
int tmp,top;
int cnt=0;
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};
}
Line count(Point x,Point y)
{
return (Line){x,y};
}
int chacheng(Point a,Point b)
{
return a.x*b.y-a.y*b.x;
}
int dis(Point a,Point b)
{
Point now = a-b;
return now.x*now.x+now.y*now.y;
}
bool cmp(Point a,Point b)
{
int now = chacheng(a-ymh,b-ymh);
if(now>0) return 1;
if(now<0) return 0;
else
{
int d1 = dis(a,ymh);
int d2 = dis(b,ymh);
return d1<d2;
}
}
void solve(int n)
{
int mn = inf,pos=0;
for (int i=1;i<=n;i++) if (a[i].y<mn ||(a[i].y==mn && a[i].x<a[pos].x)) mn=a[i].y,pos=i;
swap(a[pos],a[1]);
ymh=a[1];
sort(a+1,a+1+n,cmp);
a[n+1]=a[1];
top=1;
st[top]=a[1];
for (int i=2;i<=n+1;i++)
{
while(top>1 && chacheng(st[top]-st[top-1],a[i]-st[top-1])<=0) top--;
st[++top]=a[i];
}
for (int i=1;i<top;i++) l[++tmp]=st[i+1]-st[i];
for (int i=1;i<top;i++) x[++numx]=st[i];
}
void solve1(int n)
{
int mn = inf,pos=0;
for (int i=1;i<=n;i++) if (b[i].y<mn || (b[i].y==mn && b[i].x<b[pos].x)) mn=b[i].y,pos=i;
swap(b[pos],b[1]);
ymh=b[1];
sort(b+1,b+1+n,cmp);
b[n+1]=b[1];
top=1;
st[top]=b[1];
for (int i=2;i<=n+1;i++)
{
while(top>1 && chacheng(st[top]-st[top-1],b[i]-st[top-1])<=0) top--;
st[++top]=b[i];
}
for (int i=1;i<top;i++) l[++tmp]=st[i+1]-st[i];
for (int i=1;i<top;i++) y[++numy]=st[i];
}
int get(Point a)
{
return a.y>=0;
}
bool cmp1(Point a,Point b)
{
int x = get(a),y=get(b);
if (x!=y) return x>y;
if(chacheng(a,b)>=0) return 1;
else return 0;
}
void minkowski()
{
lyf[1]=x[1]+y[1];
cnt=1;
sort(l+1,l+1+tmp,cmp1);
for (int i=1;i<=tmp;i++) ++cnt,lyf[cnt]=lyf[cnt-1]+l[i];
cnt--;
ymh=lyf[1];
}
bool erf(Point nyd)
{
if (chacheng(lyf[cnt]-lyf[1],nyd-lyf[1])>0 || chacheng(lyf[2]-lyf[1],nyd-lyf[1])<0) return 0;
int l=1,r=cnt;
int pos=0;
while (l<=r)
{
int mid = l+r >> 1;
if (chacheng(lyf[mid]-ymh,nyd-ymh)>0 || (chacheng(lyf[mid]-ymh,nyd-ymh)==0 && dis(lyf[mid],ymh)<=dis(nyd,ymh))) pos=mid,l=mid+1;
else r=mid-1;
}
if (chacheng(lyf[pos+1]-lyf[pos],nyd-lyf[pos])>=0) return 1;
else return 0;
}
signed main()
{
n=read(),m=read(),q=read();
for (int i=1;i<=n;i++) a[i].x=read(),a[i].y=read();
for (int i=1;i<=m;i++) b[i].x=-read(),b[i].y=-read();
q=13;
solve(n);
solve1(m);
minkowski();
for (int i=1;i<=q;i++)
{
Point nyd;
nyd.x=read();
nyd.y=read();
cout<<erf(nyd)<<"\n";
}
return 0;
}