poj 1971 Parallelogram Counting

题目链接

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

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

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

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

 

 

作者: CrazyKK

ex-ACMer@hust,researcher@sensetime

说点什么

您将是第一位评论人!

提醒
wpDiscuz