题解 | 数三角形

#include <bits/stdc++.h>
// #include<unordered_map>
using namespace std;
const int N = 110;

pair<int, int> pnt[N];

int main() {
    int n;
    while (cin >> n) { // 注意 while 处理多个 case
        for(int i = 0; i < n; i++) cin >> pnt[i].first >> pnt[i].second;
        int ans = n * (n - 1) * (n - 2) / 6;
        for (int i = 0; i < n; i++) {
            map<pair<int, int>, int> kCnt;
            for (int j = i + 1; j < n; j++) {
                pair<int, int> k = {pnt[j].first - pnt[i].first, pnt[j].second - pnt[i].second};
                int gcd = __gcd(k.first, k.second);
                k.first /= gcd;
                k.second /= gcd;
                if (k.first < 0) {
                    k.first = -k.first;
                    k.second = -k.second;
                } else if (k.first == 0 && k.second < 0) {
                    k.second = -k.second;
                }
                kCnt[k]++;
            }
            for (auto& kc: kCnt) {
                if (kc.second < 2) continue;
                ans -= kc.second * (kc.second - 1) / 2;
            }
        }
        cout << ans << endl;
    }
}
// 64 位输出请用 printf("%lld")

考虑O(n^3) -> O(n^2logn)优化第三个for循环，三点有两线的斜率相同则三点共线的性质，考虑答案结构：任取三点的点对数量 减 三点共线的点对的数量，对任意点xi，枚举点xj(i < j), 维护一个计数map计算线xixj标准化的斜率相同的点xj的集合的大小cnt，用数学方法计算出集合任意两点与xi共线的数量cnt * (cnt - 1) / 2，用这个减去答案即可。