题解 | #数三角形#

思路

因为 个点互不相同，因此我们任取三个点有 种可能，而其中在一条线上的点将不能形成三角形，我们设 个点可以形成 条线，其中第 条线上有 个点，则：

于是，我们统计 个点可以构成的每条线与每条线上的点数，即可在 时间内算出三角形个数。显然，线最多为 条，故可在 时间内计算出结果。 那么，如何统计线上的点数呢？我们遍历每个点对，计算点对的直线方程，将两个点插入到对应直线的集合中即可。如果我们能在 时间内找到直线对应的集合，则点对数目即为时间复杂度，即 。

自然地，我们想到可以用哈希表存储每条直线上对应的点集。我们写出直线的两点式方程：

化简，

因此，只要确定了、 与 三个系数，就能唯一确定一条直线。但是，一条直线的三个系数并不唯一，它们同时乘以某个因子仍然满足方程。因此需要分情况确定唯一的 、、，由于点互不相同，因此 、 不同时为 。

• 若 、 为 ，此时直线方程为 ，因此置 。
• 若 、 为 ，此时直线方程为 ，因此置 。
• 若仅有 为 ，我们可以让 、 除以其最大公因数保证唯一性。
• 若仅有 为 ，我们可以让 、 除以其最大公因数保证唯一性。
• 若仅有 为 ，我们可以让 、 除以其最大公因数保证唯一性。
• 若均不为 ，我们可以让 、、 均除以其最大公因数保证唯一性。

除此之外，还需保证 、、 的正负顺序，我们可以在 存在时保证 为正，否则保证 为正。

最后，我们知道 、、，因此 、、，故 、 可用一个 15 位无符号整数表示，可用一个 30 位无符号整数表示（实际上不需要这么多位），因此可用一个 long long 存储 ((C+20000)<<30)|((B+200)<<15)|(A+200)表示一条直线，该值即为直线的哈希值。

代码

具体实现使用 hashLine 根据两点求直线哈希值，使用unordered_map存储点集，使用unordered_set对插入点去重。

#include <bits/stdc++.h>
#include <functional>
#include <ios>
using namespace std;

using ll = long long;
ll hashLine(ll x0, ll y0, ll x1, ll y1)
{
    ll A = x1-x0;
    ll B = y1-y0;
    ll C = x1*y0-x0*y1;
    if(A<0) { A=-A; B=-B;C=-C;}
    else if(A==0 && B<0) { B=-B; C=-C; }
    
    ll factor;
    if(A==0 && C==0) factor=B;
    if(A==0) factor = abs(gcd(B,C));
    else if(B==0 && C==0) factor=A;
    else if(B==0) factor = abs(gcd(A, C));
    else if(C==0) factor = abs(gcd(A,B));
    else factor = abs(gcd(A, gcd(B,C)));
    
    A/=factor;
    B/=factor;
    C/=factor;
    A+=200;
    B+=200;
    C+=20000;
    return (C<<30)|(B<<15)|A;
}

int main() {
    unordered_map<ll, unordered_set<int>> freq;
    int n;
    ios_base::sync_with_stdio(false);
    cin>>n;
    vector<pair<int,int>> pts(n);
    for(auto &p: pts) cin>>p.first>>p.second;
    for(int i=0;i<pts.size();++i) for(int j=i+1;j<pts.size();++j){
        ll line = hashLine(pts[i].first, pts[i].second, pts[j].first, pts[j].second);
        freq[line].insert(((pts[i].first+100)<<15)|(pts[i].second+100));
        freq[line].insert(((pts[j].first+100)<<15)|(pts[j].second+100));
    }
    ll cnt = n*(n-1)*(n-2)/6;
    for(auto &p: freq) {
        ll m = p.second.size();
        cnt -= m*(m-1)*(m-2)/6;
    }
    cout<<cnt<<endl;
    return 0;
}

• 时间复杂度：，hashLine可在常量时间内完成，因此二重循环花费 时间。
• 空间复杂度：，哈希表中所有集合中的总点数为 。