gougou1032

从 Trac 迁移的文章

这是从旧校内 Wiki 迁移的文章，可能存在一些样式问题，您可以向 memset0 反馈。

原文章内容如下：

1032
Counting Rectangles

http://acm.zju.edu.cn/onlinejudge/showProblem.do?problemCode=1426

8 2006-07-27 01:33:41 00:00:90 908K C++ glimpse

   又一道被我暴殄的题。写了7kb的代码，TLE呀TLE，费了九牛二虎之力才搞定。看了一下ranklist，真是汗颜呀。因为我的代码实在是太慢了，也不好意思在这里多说什么。我用的方法比较朴素：先把所有的边的组合找出来，把它们分成水平和竖直两组，每次从两组各取出两条边，看能不能组成矩形。

   这样说说比较简单，但实现起来，还是有比较多麻烦的。一个是怎么得到所有变得组合，一个是怎么判四条边可以组成矩形？

   唉，我就不继续误人子弟了。

----

我的一个正确而简单的复杂度O(n^3^)的算法：把线分成两组，水平和垂直的。O(n^2^)枚举所有两条水平线的组合，O(n)统计与这两条水平线都相交的垂直线的个数k，那么ans += k * (k - 1) / 2。

1032

Counting Rectangles

http://acm.zju.edu.cn/onlinejudge/showProblem.do?problemCode=1426

8 2006-07-27 01:33:41 00:00:90 908K C++ glimpse

又一道被我暴殄的题。写了7kb的代码，TLE呀TLE，费了九牛二虎之力才搞定。看了一下ranklist，真是汗颜呀。因为我的代码实在是太慢了，也不好意思在这里多说什么。我用的方法比较朴素：先把所有的边的组合找出来，把它们分成水平和竖直两组，每次从两组各取出两条边，看能不能组成矩形。

这样说说比较简单，但实现起来，还是有比较多麻烦的。一个是怎么得到所有变得组合，一个是怎么判四条边可以组成矩形？

唉，我就不继续误人子弟了。

---

我的一个正确而简单的复杂度O(n³)的算法：把线分成两组，水平和垂直的。O(n²)枚举所有两条水平线的组合，O(n)统计与这两条水平线都相交的垂直线的个数k，那么ans += k * (k - 1) / 2。