现在的位置: 首页 > 综合 > 正文

POJ 1971 Parallelogram Counting

2014年07月20日 ⁄ 综合 ⁄ 共 297字 ⁄ 字号 评论关闭

题目链接 :  http://poj.org/problem?id=1971

题意 : 给你n(n <= 1000)个点, 问你有多少个平行四边形。

思路 : 一开始我是枚举每一条有向边, 因为两条边相等且方向一样的话就可以够成一个平行四边形,数出所有的之后减去一些三点一线的, 然后除2(一个四边形有两对平行边)就可以获得正确答案了。O(n ^ 2 * log (n ^ 2))的复杂度, 但是可能常数有点大(我实现需要两次排序, 并且还要二分查找)吧还是我写挫了, 一直TLE,后来发现其实可以用另一个判断平行四边形的方法来做这一道题目 : 平行四边形的对角连线互相平分。 这样只要枚举中点,对于中点一次排序就可以完成了, 然后就变成简单题了。

抱歉!评论已关闭.