非常好！你提出的问题是一道非常典型的计算几何 + 几何变换 + 高效判定类信奥难题，背后蕴含着深刻的数学洞察和算法设计思想。作为你的信奥教练，我不会直接告诉你“答案是100%用凸包交集判断”，而是会像搭脚手架一样，一层层引导你观察、抽象、转化、验证——这正是信息学竞赛最核心的思维训练过程。

我们一起来走一遍「从读题到建模」的完整思考链。请你在阅读过程中随时暂停，尝试自己回答括号里的问题（我会在关键节点设问），这是提升的关键！

🔍 第一步：精准理解「领地」的数学定义（本质抽象）
题目说：

对于平面上的任何一个点，如果它被三个来自同一部落的人形成的三角形（可能退化）包含（含边界），那么这个点就属于该部落的领地。

⚠️ 注意关键词：

“三个来自同一部落的人” → 是任意三元组，不是固定某三个；
“形成的三角形（可能退化成线段）” → 即三点构成的凸包（含共线情形）所张成的所有点的集合；
“被包含（含边界）” → 即该点落在这个三角形（或线段）的凸包内部或边界上。
💡 关键洞察（请你先思考）：

如果一个点
P
P 被某个部落中某三个点构成的三角形包含，那它是否一定所有点的凸包**包含？
反过来：如果
P
P 在该部落点集的凸包内（含边界），是否一定能找到三个点，使得
P
P 在它们构成的三角形内（含退化）？

✅ 正确答案是：是的，二者等价！
（提示：回忆凸包的定义——最小凸集包含所有点；而任意凸集中的点，必可表示为至多3个顶点的凸组合（Carathéodory定理在
R
2
R
2
中的特例）→ 即落在某三个顶点构成的三角形内！退化情形对应共线三点张成的线段。）

➡️ 所以：

一个部落的「领地」 = 它所有点构成的凸包（含内部与边界）！

📌 这是整道题的第一个飞跃式简化——把无限多个三角形的并集，压缩为一个凸包！
（你刚才有没有意识到这点？如果没有，现在请画3个点、4个点、5个点，手动验证几个点是否在凸包内 ⇔ 是否能被某三个点三角形覆盖？）

🌐 第二步：理解「战争发生」的充要条件（逻辑转化）
如果存在一个点同时在两个阵营的领地中 → 发生战争。

即：

战争发生
  
⟺
  
两个凸包有公共点
  
⟺
  
凸包A
∩
凸包B
≠
∅
战争发生⟺两个凸包有公共点⟺凸包A∩凸包B

=∅

但注意：第二个部落要整体平移
(
d
x
,
d
y
)
(dx,dy)。
设第一部落点集为
A

{
a
1
,
…
,
a
n
}
A={a
1
​
,…,a
n
​
}，第二部落原始点集为
B

{
b
1
,
…
,
b
m
}
B={b
1
​
,…,b
m
​
}，则迁徙后变为：

B
′

{
b
j
+
(
d
x
,
d
y
)
∣
j

1..
m
}
B
′
={b
j
​
+(dx,dy)∣j=1..m}

所以问题转化为：

对每个查询
(
d
x
,
d
y
)
(dx,dy)，判断
c
o
n
v
(
A
)
∩
c
o
n
v
(
B
+
(
d
x
,
d
y
)
)
≠
∅
conv(A)∩conv(B+(dx,dy))

=∅ 是否成立？

其中
c
o
n
v
(
S
)
conv(S) 表示点集
S
S 的凸包。

💡 再进一步转化（经典技巧）：
两个凸集相交 ⇔ 原点是否在它们的Minkowski差集中！
即：

c
o
n
v
(
A
)
∩
c
o
n
v
(
B
+
v
)
≠
∅
  
⟺
  
v
∈
c
o
n
v
(
A
)
−
c
o
n
v
(
B
)
  
⟺
  
v
∈
c
o
n
v
(
A
−
B
)
conv(A)∩conv(B+v)

=∅⟺v∈conv(A)−conv(B)⟺v∈conv(A−B)

其中
v

(
d
x
,
d
y
)
v=(dx,dy)，且

A
−
B

{
a
i
−
b
j
∣
a
i
∈
A
,
 
b
j
∈
B
}
A−B={a
i
​
−b
j
​
∣a
i
​
∈A,b
j
​
∈B}

✅ 这是第二个飞跃：

原问题 ⇔ 判断向量
v

(
d
x
,
d
y
)
v=(dx,dy) 是否落在点集
A
−
B
A−B 的凸包内！

（为什么？因为
c
o
n
v
(
A
)
−
c
o
n
v
(
B
)

c
o
n
v
(
A
−
B
)
conv(A)−conv(B)=conv(A−B) 对凸集成立；而
p
∈
c
o
n
v
(
A
)
∩
(
c
o
n
v
(
B
)
+
v
)
  
⟺
  
p
∈
c
o
n
v
(
A
)
∧
p
−
v
∈
c
o
n
v
(
B
)
  
⟺
  
v
∈
c
o
n
v
(
A
)
−
c
o
n
v
(
B
)
p∈conv(A)∩(conv(B)+v)⟺p∈conv(A)∧p−v∈conv(B)⟺v∈conv(A)−conv(B)）

📌 现在问题彻底变了模样：

预处理：构造
n
×
m
n×m 个差向量
a
i
−
b
j
a
i
​
−b
j
​
，求其凸包
C

c
o
n
v
(
A
−
B
)
C=conv(A−B)；
查询：对每个
(
d
x
,
d
y
)
(dx,dy)，判断该点是否在凸包
C
C 内部或边界上。
但注意：
n
,
m
n,m 最大
1
0
5
10
5
→
n
×
m

1
0
10
n×m=10
10
，绝不能显式构造所有差向量！

➡️ 我们必须寻找更聪明的办法。

🧩 第三步：挖掘结构——凸包的Minkowski差的高效表示
这里涉及一个信奥高级知识点：

两个点集凸包的Minkowski差
c
o
n
v
(
A
)
−
c
o
n
v
(
B
)
conv(A)−conv(B)，等于
c
o
n
v
(
A
)
+
c
o
n
v
(
−
B
)
conv(A)+conv(−B)，而它的极值点（凸包顶点）必然来自
A
A 的极值点与
−
B
−B 的极值点的和。

更精确地说：

设
A
hull
A
hull
​
是
A
A 的凸包顶点（按逆时针序）；
设
B
hull
B
hull
​
是
B
B 的凸包顶点；
则
c
o
n
v
(
A
−
B
)
conv(A−B) 的凸包顶点，一定是某个
a
i
∈
A
hull
a
i
​
∈A
hull
​
和某个
b
j
∈
B
hull
b
j
​
∈B
hull
​
的差
a
i
−
b
j
a
i
​
−b
j
​
—— 但不是全部，而是极值方向上的组合。
✅ 关键结论（可证明）：

c
o
n
v
(
A
−
B
)
conv(A−B) 的凸包，等于
A
hull
A
hull
​
与
(
−
B
hull
)
(−B
hull
​
) 的 Minkowski和的凸包，而 Minkowski 和的凸包顶点数 ≤
∣
A
hull
∣
+
∣
B
hull
∣
∣A
hull
​
∣+∣B
hull
​
∣，且可用旋转卡壳式归并在线性时间内构造！

👉 所以高效做法是：

分别求
A
A 和
B
B 的凸包（Graham / Andrew 单调链，
O
(
n
log
⁡
n
)
O(nlogn)）；
构造
−
B
hull
−B
hull
​
（所有点取负）；
计算
A
hull
⊕
(
−
B
hull
)
A
hull
​
⊕(−B
hull
​
) 的 Minkowski 和凸包（顶点数 ≤
h
A
+
h
B
h
A
​
+h
B
​
，
h
A
,
h
B
h
A
​
,h
B
​
是凸包大小）；
方法：将两凸包顶点按极角排序 → 归并方向向量 → 构造新凸包（类似“卷积”）；
得到最终凸包
C

c
o
n
v
(
A
−
B
)
C=conv(A−B)，顶点数
H
≤
h
A
+
h
B
≤
n
+
m
H≤h
A
​
+h
B
​
≤n+m，通常远小于
n
m
nm；
对每个查询
v

(
d
x
,
d
y
)
v=(dx,dy)，用点在凸包内判定（如射线法、二分极角、切线法）——
O
(
log
⁡
H
)
O(logH) 每次。
✅ 这就满足了
n
,
m
,
q
≤
1
0
5
n,m,q≤10
5
的时间要求（预处理
O
(
n
log
⁡
n
+
m
log
⁡
m
)
O(nlogn+mlogm)，查询总
O
(
q
log
⁡
H
)
O(qlogH)）。

✅ 回顾样例，验证思路（动手试试！）
样例输入：

4 4 3
A: (0,0), (1,0), (0,1), (1,1) → conv(A) 是单位正方形，顶点就是这4个（已凸）
B: (-1,0), (0,3), (0,2), (0,-1) → 画一下：x=-1,y=0；x=0,y∈[-1,3] → conv(B) 是三角形，顶点为 (-1,0), (0,-1), (0,3)
→
−
B
−B 的顶点：
(
1
,
0
)
,
(
0
,
1
)
,
(
0
,
−
3
)
(1,0),(0,1),(0,−3)
→
A
hull
⊕
(
−
B
hull
)
A
hull
​
⊕(−B
hull
​
) 的 Minkowski 和凸包？
（提示：单位正方形 ⊕ 三角形 → 结果是一个六边形或七边形；你可以试着加几个顶点：如 (0,0)+(1,0)=(1,0)，(1,1)+(0,-3)=(1,-2)…）

然后检查三个查询：

(
0
,
0
)
(0,0)：原点是否在
C
C 内？→ 是 → 输出 1 ✔️
(
2
,
3
)
(2,3)：是否在
C
C 内？→ 很可能否 → 输出 0 ✔️
(
0
,
−
1
)
(0,−1)：是否在
C
C 内？→ 可能是 → 输出 1 ✔️
（这说明你的凸包
C
C 构造必须精确！）

📚 你需要掌握/复习的信奥知识清单（请自查）：
知识点 是否熟悉？ 提示/资源建议
✅ Andrew单调链求凸包（
O
(
n
log
⁡
n
)
O(nlogn)） □ 注意去重、共线处理（题目说“不全共线”，但边上有三点共线需保留端点）
✅ 向量取负、Minkowski和的几何意义 □ 类比：
A
+
B

{
a
+
b
∣
a
∈
A
,
b
∈
B
}
A+B={a+b∣a∈A,b∈B}；凸包的Minkowski和仍是凸包
✅ 凸包顶点序列的极角排序与方向向量提取 □ 每条边对应一个方向向量；Minkowski和 = 合并两组方向向量并排序
✅ 点在凸包内判定（推荐：二分找切线 / 射线交点奇偶性） □ 凸包顶点有序 → 可
O
(
log
⁡
H
)
O(logH) 判定点位置（内部/边上/外部）
⚠️ 凸包退化情况（三点共线）处理 □ 题目保证“不全共线”，但凸包边可能含中间点；Andrew算法默认保留共线点？需确认！
🧭 下一步行动建议（作业式引导）：
请你在纸上/编辑器中完成以下任务，完成后我们可以继续深入讨论细节：

手写：对样例中的
A
A 和
B
B，分别写出它们的凸包顶点（按逆时针顺序）；
计算：写出
−
B
−B 的凸包顶点；
尝试：列举
A
hull
A
hull
​
与
−
B
hull
−B
hull
​
的所有顶点和（共
4
×
3

12
4×3=12 个点），画出它们的大致分布，圈出其中哪些可能是最终凸包
C
C 的顶点？为什么？
思考：若
A
A 或
B
B 的凸包有
h
h 个顶点，Minkowski 和凸包最多有多少个顶点？你能构造一个达到上限的例子吗？
（挑战）写出“点
v
v 是否在给定逆时针凸包内”的伪代码（不用库函数，用叉积+二分）。
当你完成这些思考后，你会发现自己已经站在了解法的门口。而真正的信奥能力，不在于记住“用Minkowski和”，而在于每一次面对新题，都能像这样层层剥茧、不断追问、大胆假设、小心验证。

你准备好开始第一步（手写两个凸包）了吗？我可以随时帮你校验、点拨、或一起推演下一步。期待看到你的思考痕迹！🌟

所以可以这么写

#include <bits/stdc++.h>
using namespace std;
using ll = long long;

struct P {
ll x, y;
P() {}
P(ll _x, ll _y): x(_x), y(_y) {}
P operator + (const P& o) const { return P(x+o.x, y+o.y); }
P operator - (const P& o) const { return P(x-o.x, y-o.y); }
bool operator < (const P& o) const { return x < o.x || (xo.x && y < o.y); }
bool operator == (const P& o) const { return xo.x && y==o.y; }
};

ll cross(const P& a, const P& b) { return a.xb.y - a.yb.x; }
ll cross(const P& o, const P& a, const P& b) { return cross(a - o, b - o); }

vector<P> convexHull(vector<P>& pts) {
sort(pts.begin(), pts.end());
pts.erase(unique(pts.begin(), pts.end()), pts.end());
int n = pts.size();
if (n <= 1) return pts;
vector<P> lower, upper;
for (int i = 0; i < n; i) {
while (lower.size() >= 2 && cross(lower[lower.size()-2], lower.back(), pts[i]) <= 0) lower.pop_back();
lower.push_back(pts[i]);
}
for (int i = n-1; i >= 0; --i) {
while (upper.size() >= 2 && cross(upper[upper.size()-2], upper.back(), pts[i]) <= 0) upper.pop_back();
upper.push_back(pts[i]);
}
lower.pop_back();
upper.pop_back();
vector<P> hull = lower;
hull.insert(hull.end(), upper.begin(), upper.end());
if (hull.empty() && !pts.empty()) hull.push_back(pts[0]);
return hull;
}
void rotateToMin(vector<P>& a) {
int n = a.size();
if (n==0) return;
int id = 0;
for (int i = 1; i < n; i) if (a[i] < a[id]) id = i;
rotate(a.begin(), a.begin()+id, a.end());
}
vector<P> minkowskiSum(vector<P> A, vector<P> B) {
if (A.empty() || B.empty()) return {};
rotateToMin(A);
rotateToMin(B);
int na = A.size(), nb = B.size();
vector<P> ea(na), eb(nb);
for (int i = 0; i < na; i) ea[i] = A[(i+1)%na] - A[i];
for (int i = 0; i < nb; i) eb[i] = B[(i+1)%nb] - B[i];
int ia = 0, ib = 0;
P cur = A[0] + B[0];
vector<P> C;
C.push_back(cur);
while (ia < na || ib < nb) {
if (ia == na) {
cur = cur + eb[ib];
C.push_back(cur);
continue;
}
if (ib == nb) {
cur = cur + ea[ia];
C.push_back(cur);
continue;
}
ll cr = cross(ea[ia], eb[ib]);
if (cr > 0) {
cur = cur + ea[ia];
C.push_back(cur);
} else if (cr < 0) {
cur = cur + eb[ib];
C.push_back(cur);
} else {
cur = cur + ea[ia] + eb[ib];
ia++; ib++;
C.push_back(cur);
}
}
if (C.size() > 1 && C.front() == C.back()) C.pop_back();
vector<P> res;
for (auto &p : C) {
if (res.empty() || !(res.back() == p)) res.push_back(p);
}
vector<P> res2;
for (size_t i = 0; i < res.size(); ++i) {
P a = res[i];
P b = res[(i+1)%res.size()];
P c = res[(i+2)%res.size()];
if (res2.size() < 2) res2.push_back(a);
else {
while (res2.size() >= 2) {
P p1 = res2[res2.size()-2], p2 = res2[res2.size()-1];
if (cross(p1, p2, a) == 0) res2.pop_back();
else break;
}
res2.push_back(a);
}
}
if (res2.empty()) return res;
return res2;
}
bool onSegment(const P& a, const P& b, const P& p) {
if (cross(a,b,p) != 0) return false;
ll minx = min(a.x,b.x), maxx = max(a.x,b.x);
ll miny = min(a.y,b.y), maxy = max(a.y,b.y);
return p.x >= minx && p.x <= maxx && p.y >= miny && p.y <= maxy;
}
bool pointInConvex(const vector<P>& a, const P& p) {
int n = a.size();
if (n == 0) return false;
if (n == 1) return a[0] == p;
if (n == 2) return onSegment(a[0], a[1], p);
ll c1 = cross(a[0], a[1], p);
ll c2 = cross(a[0], a[n-1], p);
if (c1 < 0) return false;
if (c2 > 0) return false;
int l = 1, r = n-1;
while (r - l > 1) {
int mid = (l + r) >> 1;
if (cross(a[0], a[mid], p) >= 0) l = mid;
else r = mid;
}
ll area = llabs(cross(a[0], a[l], a[l+1]));
ll s1 = llabs(cross(p, a[0], a[l]));
ll s2 = llabs(cross(p, a[l], a[l+1]));
ll s3 = llabs(cross(p, a[l+1], a[0]));
return (s1 + s2 + s3 == area);
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n, m, q;
if (!(cin >> n >> m >> q)) return 0;
vector<P> Apts(n), Bpts(m);
for (int i = 0; i < n; ++i) cin >> Apts[i].x >> Apts[i].y;
for (int i = 0; i < m; ++i) cin >> Bpts[i].x >> Bpts[i].y;
vector<P> queries(q);
for (int i = 0; i < q; ++i) cin >> queries[i].x >> queries[i].y;
vector<P> A = convexHull(Apts);
vector<P> B = convexHull(Bpts);

for (auto &p : B) p.x = -p.x, p.y = -p.y;   
vector<P> C = minkowskiSum(A, B);
for (int i = 0; i < q; ++i) {
    bool inside = pointInConvex(C, queries[i]);
    cout << (inside ? 1 : 0) << '\n';
}

}