题解 | #E 小红的平行四边形#

由于需要三个点才能计算平行四边形面积，枚举点时间复杂度不符合要求，所以我们考虑枚举边。我们对每两个点构成的向量用哈希表分组，注意向量的方向性。这里不用存下每组所有的向量然后进行排序，只需要维护一个最大值和最小值，不过需要用到一点简***面几何。

我们将当前分组的向量平移到原点，由于需要求每组向量之间能够组成的最大面积（如图中的红色面积），这可以拆成两个平行四边形面积之和（如图中绿色的S1和S2)。由于S是用叉积计算的（带正负），所以其实红色面积是S2 - S1。因此，我们只需要维护每组S的最大值和最小值，两者之差即为该组的最大面积。

from collections import defaultdict
n = int(input())
a = [list(map(int, input().split())) for _ in range(n)]
mx, mn = defaultdict(lambda: -10 ** 18), defaultdict(lambda: 10 ** 18)
res = 0
for i in range(n):
    x1, y1 = a[i]
    for j in range(i):
        x2, y2 = a[j]
        dx, dy = x1 - x2, y1 - y2
        if dx > 0: dx, dy = -dx, -dy
        s = dy * x1 - dx * y1
        p = (dx, dy)
        mx[p], mn[p] = max(mx[p], s), min(mn[p], s)
        res = max(res, mx[p] - mn[p]) 
print(str(res) + '.0' if res else -1)