洛谷4557 [JSOI2018]战争
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$ 内，二分出极角相邻的点...
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$ 内，二分出极角相邻的点...