ConvexPolygonGame

作者：袁伟强

关键词：博弈 计算几何

题目简述

给一个格点凸多边形，两个人轮流操作。每次操作需要画一个格点凸多边形，满足该多边形的顶点在上一个多边形的内部或边界上，但不能和上一个多边形的顶点重合。求是先手必胜还是后手必胜。

$1\leq N \leq 50​$（$N​$为初始时多边形顶点数）

$-10^5\leq X,Y\leq 10^5$（$X,Y$为顶点坐标）

结论及其证明

这题有一个结论：如果先手一开始可以操作，那么是先手必胜，否则是后手必胜。下面给出证明。

如果先手一开始无法操作，肯定是后手必胜，设$W$为这类多边形的集合。对于一个格点凸多边形$a$，记$Suff_{a}$为通过$a$能得到的多边形组成的集合。由于被新多边形包含的格点必然也被原多边形包含，所以对于任意$x\in Suff_{a}$，都有$Suff_{x}\subseteq Suff_{a}$ 。由于$a$内的格点数目是有限的，所以$a$内的格点数目是有限的，即$Suff_{a}$是有限集。

下面我们采用反证法，假设存在$x\notin W$，且对于$y\in Suff_{x}$，均有$y\notin W$。我们称一个序列$b_{1},b_{2},...,b_{n}$为操作序列，当且仅当对任意$1\leq k \leq n-1$，均有$b_{k+1}\in Suff_{b_k}$。下面我们用归纳法证明我们可以构造出任意长度的操作序列且满足$b_{1}=x$。$n=1$时，$b_{1}=x$为操作序列。已知当$n=k$时，$b_{1}=x,b_{2},...,b_{k}$为操作序列，则当$n=k+1$时，由于$b_{k}\in Suff_{b_{k-1}}\subseteq Suff_{b_{k-2}}\subseteq...\subseteq Suff_{b_{1}}$，所以$b_{k}\notin W$，即$Suff_{b_k}\neq \varnothing$，任取$b_{k+1}\in Suff_{b_{k}}$，则$b_{1}=x,b_{2},...,b_{k},b_{k+1}$为操作序列。对于任意$i<j$，$b_{j}\in Suff_{b_{j-1}}\subseteq Suff_{b_{j-2}}\subseteq...\subseteq Suff_{b_{i}}$，于是$b_{i}\neq b_{j}$。而对于任意$k>1$，均有$b_{k}\in Suff_{b_{1}}$，故$Suff_{b_{1}}$为无限集，这与之前得到的结论相矛盾。至此，该结论得证。

判断一个多边形$a$是否属于$W$，只需要判断$a$内的格点是否共线。若共线，显然$a\in$W；若不共线，只要找到任意不共线的三点就可以组成三角形，则$a\notin W$。

算法

现在我们的问题变成了判断该多边形内的格点是否共线。注意到一条线上的格点数不超过$200001$，我们可以直接去统计多边形内的所有格点，一旦超过$200001$，就可以直接break。如何去找到这些点？我们可以直接暴力枚举$X$，与$x=X$相交的边最多只有$2$条。我们求出这两条边与$x=X$的交点，将两个交点之间的格点加入到我们所要求的点集中（注意排除顶点）。找到所有点后，只需取前两个点，判断其他点是否都与它们共线即可，当然该过程可以在加点的时候完成。判断共线可以用叉积。

时间复杂度$O(N+100000)​$。