poj 1971 Parallelogram Counting

2016年11月22日 0 作者 CrazyKK

题目链接

题意:给出n(n<=1E3)个不同的点,问最多组成多少个平行四边形。

思路:这道题的关键是,对于平行四边形的判断条件,要利用平行四边形对角线的交点平分两条对角线的性质。

也就是说,如果两条线段的对角线重合,那么一定可以组成一个平行四边形。

因此统计中点的位置即可,复杂度n*n*lg(n*n)