FindPolygons

作者 : 翁伊嘉

关键词 : 数学，勾股定理，暴力

题目简述

输入整数$L$，在平面直角坐标系中找出一个多边形，满足：

• 顶点均在整点上
• 周长恰为$L$
• 边数尽量少
• 在满足以上条件的前提下，最长边与最短边长度之差尽量小

输出其最长边与最短边长度之差。

$L \le 5000$

分析

能够发现以下性质：

每条边的长度均为整数

由于每条边的两个端点都在整点上，每条边的长度都是$\sqrt{x}$的形式，其中$x$是整数。 可以证明，若$L = \sqrt{x_1} + \sqrt{x_2} + \cdots \sqrt{x_n}$中，存在$\sqrt{x_i}$为无理数，$L$也不可能为有理数。 在这里可以找到具体的证明。

$L$为奇数时不存在满足条件的多边形

由于每条边的长度都是整数，$L$为奇数时，存在奇数条边的长度为奇数。

对于一条边，设它的两个端点分别为$(x_0, y_0), (x_1, y_1)$,根据勾股定理，边长$c$满足$c ^ 2 = (x_1 - x_0) ^ 2 + (y_1 - y_0) ^ 2$。

若$c$为奇数，则$|x_1 - x_0|$与$|y_1 - y_0|$中恰有一个为奇数。即，从点$(x_0, y_0)$走到点$(x_1, y_1)$, 所在点的纵横坐标之和$x + y$的奇偶性发生变化。

若$c$为偶数，则$|x_1 - x_0|,|y_1 - y_0|$的奇偶性相同，因此走一条长度为偶数的边，所在点的纵横坐标之和$x + y$的奇偶性不发生变化。

从多边形的一个顶点出发，沿着所有边走一遍走回这个顶点。若经过了奇数条长度为奇数的边，$x + y$的奇偶性应当发生变化。但是实际上，由于回到了同一个点，$x + y$的奇偶性不变。于是，$L$为奇数时不存在满足条件的多边形。

$L = 2$时无解

$L \ge 4$且$L$为偶数时，一定可以找到满足条件的矩形，即所求多边形的边数不超过$4$

令矩形的一边为$a$, 另一边为$L / 2 - a$，就得到了一个满足条件的矩形。

当$L$能被$4$整除时，可以找到一个满足条件的正方形，最长边最短边长度之差为$0$。否则，长度之差最小可以为$1$。

接下来，只要对于$L$为偶数的情况，验证是否存在满足条件的三角形，并在所有这样的三角形中取最长边最短边长度之差最小的一个。

算法一

无论三角形的形状如何，都可以通过平移/轴对称，令它的一个顶点与原点重合，剩下两个顶点位于第一象限内/$x$轴正半轴上/$y$轴正半轴上。

考虑枚举剩下两个顶点的位置。由于边长需要是整数，第一象限内可供选择的顶点个数只有$10134$个。

在这些顶点中枚举剩下两个顶点的位置，判断一下是否能构成周长恰好为$L$的三角形即可。

复杂度$O({10134 \choose 2})$

算法二

枚举一个点的位置$(x, y)$, 枚举从$(x, y)$出发的另一条边的长度$b$，然后计算出第三个顶点的位置，看一下是不是整点。

复杂度$O(10134 * L / 2)$

算法三

打表大法，复杂度$O(1)$.

参考资料

SRM599 - TopCoder Wiki