10月Day30

思路 因为 个点互不相同，因此我们任取三个点有 种可能，而其中在一条线上的点将不能形成三角形，我们设 个点可以形成 条线，其中第 条线上有 个点，则： 于是，我们统计 个点可以构成的每条线与每条线上的点数，即可在 时间内算出三角形个数。显然，线最多为 条，故可在 时间内计算出结果。 那么，如何统计线上的点数呢？我们遍历每个点对，计算点对的直线方程，将两个点插入到对应直线的集合中即可。如果我们能在 时间内找到直线对应的集合，则点对数目即为时间复杂度，即 。 自然地，我们想到可以用哈希表存储每条直线上对应的点集。我们写出直线的两点式方程： 化简， 因此，只要确定了、 与...