team2012-D1-sol-0005

从 Trac 迁移的文章

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

原文章内容如下：

=== 解题思路 ===
直接数三角形很复杂(的样子), 那么反过来思考: 求三点不会构成三角形的情况, 即退化为一条线段的情况. 然后用总方案数(包括不退化和退化的)减一下就好了. 比赛的时候因为漏考虑了一种情况, WA到死. 赛后改成了枚举线段的两个端点, 然后可以 O(1) 的算出来在这种情况下有多少种三点共线的情况, 瞬间就搞定了, 代码也简单易懂.

解题思路

直接数三角形很复杂(的样子), 那么反过来思考: 求三点不会构成三角形的情况, 即退化为一条线段的情况. 然后用总方案数(包括不退化和退化的)减一下就好了. 比赛的时候因为漏考虑了一种情况, WA到死. 赛后改成了枚举线段的两个端点, 然后可以 O(1) 的算出来在这种情况下有多少种三点共线的情况, 瞬间就搞定了, 代码也简单易懂.