题解(非官方)

greyishsong 2019-07-24 20:42:03

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

任意两个不共线的向量可以唯一确定一个三角形,而这个三角形的面积就是,所以题目保证了为整数。

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

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

  • 保证,即点C在点D的右上(或正上、正右),遍历所有可能的

  • ,这说明了一个为长的矩形补上个单位正方形面积正好是,若则找到了一组解,否则就是超出了坐标范围。

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

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

  • 如果存在解及其对应的,则必然有。假设是从大矩形中去掉的小矩形,那么可以表示为,从而可以构造一个等价的方案:从大矩形中去掉一个的矩形,然后将原先的小矩形变为

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

代码写起来不难,就不贴了,只是有个小问题:考虑到这个条件,是有可能超出int范围的,注意使用long long即可。