team2012-D1-sol-0047

从 Trac 迁移的文章

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

原文章内容如下：

这题是道挺不错的计数问题. 首先枚举每一种 h * w 的矩形 (0 <= h <= H, 0 <= w <= W). 对于枚举的每种矩形, 都算一下内接锐角三角形的个数. 分为两种情况, 一种是恰有两个顶点在矩形顶点上, 另一种是恰有一个顶点在矩形顶点上. 两种情况都需要列一个方程算一下使得构成的三角形是锐角三角形顶点的取值范围. 不过学姐这题数据范围太弱了. 我是直接 N^2^ 枚举的. 所以时间复杂度会多一维. 总体是 O(N^4^) 的. (0 <= H, W <= N = 100). 正解是 O(N^3^) 的.

这题是道挺不错的计数问题. 首先枚举每一种 h * w 的矩形 (0 <= h <= H, 0 <= w <= W). 对于枚举的每种矩形, 都算一下内接锐角三角形的个数. 分为两种情况, 一种是恰有两个顶点在矩形顶点上, 另一种是恰有一个顶点在矩形顶点上. 两种情况都需要列一个方程算一下使得构成的三角形是锐角三角形顶点的取值范围. 不过学姐这题数据范围太弱了. 我是直接 N² 枚举的. 所以时间复杂度会多一维. 总体是 O(N⁴) 的. (0 <= H, W <= N = 100). 正解是 O(N³) 的.