题解（非官方）

本题的输入中给的是$2\times S$是一个有益的提示：计算面积的时候应当考虑用向量叉积。

任意两个不共线的向量$\vec a,\vec b$可以唯一确定一个三角形，而这个三角形的面积就是$2S=|\vec a \times \vec b|=|x_1y_2-x_2y_1|$，所以题目保证了$2\times S$为整数。

由于自由向量是可以随意平移的，我们可以直接将一个点放在$(0,0)$处，只考虑构造剩下的两个点$A(x_1,y_1),B(x_2,y_2)$。构造出一组解的关键是：寻找到两对x,y使得其乘积之差是面积的两倍。这个问题可以转化为：寻找两个顶点为整点的矩形，使得两个矩形的面积之差是$2\times S$，这两个矩形的右上顶点是$C(x_1,y_2)和D(x_2,y_1)$。直接由原点和两坐标轴上的点构成直角三角形的这一类特解很简单，可以$O(N)$判定是否存在，故下面只讨论$A,B$至少一个点不在坐标轴上的情况。

提供一种构造方式，按照“大矩形中去掉一个小矩形”的方式：

• 保证$x_1\geq x_2 \wedge y_2\geq y_1$，即点C在点D的右上（或正上、正右），遍历所有可能的$x_1$，

• $\forall x_1\in [1,N],令l=2S \, \mathrm{div} \, x_1,\, r=2S \, \mathrm{mod} \, x_1$，这说明了一个$x_1\times l$为长的矩形补上$r$个单位正方形面积正好是$2\times S$，若$l+1\leq N$则找到了一组解$A(x_1,1),B(x_1-r,l+1)$，否则就是超出了坐标范围。

• 当遍历了所有可能的$x_1$之后如果仍然找不到解，那一定无解。

下面证明一下这种构造方式的正确性：

• 如果存在解$A(x_1,y_1),B(x_2,y_2)$及其对应的$C(x_1,y_2),D(x_2,y_1)$，则必然有$y_2\geq l+1$。假设$\Delta S=x_2y_1$是从大矩形中去掉的小矩形，那么可以表示为$\Delta S=\Delta S\, \mathrm{mod}\, x_1+\Delta S\, \mathrm{div}\, x_1$，从而可以构造一个等价的方案：从大矩形$S=x_1y_2$中去掉一个$x_1\times (\Delta S\, \mathrm{div}\, x_1)$的矩形，然后将原先的小矩形变为$\Delta S'=(\Delta S\, \mathrm{mod}\, x_1)\times 1$。

• 由此，如果存在一组解，那么必然存在上述方法可以构造出的解。同时，因为任意解必满足$x_1\in [1,N]$，所以只要存在解，该方法必能构造出解。反之，若该方法构造失败，则此时问题无解。

代码写起来不难，就不贴了，只是有个小问题：考虑到$N,M\leq 1,000,000$这个条件，$2\times S$是有可能超出int范围的，注意使用long long即可。