题解：AT_abc418_e [ABC418E] Trapezium

· · 题解

题意

给你一些不共线的点，求他们能组成多少梯形。

这里的梯形是包括平行四边形的。

题解

直接枚举四个点会炸。我们考虑梯形的一对边是平行的，所以我们可以把所有平行的边归类。

题目保证没有三个点共线，所以我们直接计算每种边有多少条就可以了，每种的方案是 \frac{k(k - 1)}{2}。

然后你发现自己连第一个样例都过不去。问题在于，如果存在一个平行四边形，那么他会被横着竖着算两次，因此我们还需要计算所有的平行四边形的数量。这个其实和梯形是一样的，只不过我们需要把所有既平行又相等的边归为一类，统计所有的平行四边形数量。但是这样依然存在计算两次的问题，所以我们把得到的答案再减半就是平行四边形的数量了。

实现上可以用 unordered_map，但是斜率如果直接用浮点数的话会炸。这里提供两种方法：

  1. 使用 unordered_map 的自定义比较功能，判断两个斜率的差的绝对值。代码

  2. 使用有理数表示斜率，然后自定义哈希。代码

实现起来，第一种比较简单，常数较小；第二种比较保险（当然前提是你的哈希写的比较好，没有碰撞的风险。），常数略大。