题解【P7676 [COCI2013-2014#5] TROKUTI】

kouylan · 2021-10-13 19:43:23 · 题解

给定平面上的若干条直线，求围成的三角形的个数。

首先考虑什么样的三条直线可以围成一个三角形。三条直线必须互不平行，也就是三条直线的斜率不相等。

那么我们可以枚举直线 x，假设斜率为 k，那我们要求出斜率小于 k 的直线个数和斜率大于 k 的直线个数，两者相乘就是直线 x 的答案。最后再把这些相加即可。

这样做可以保证不重不漏，因为计算每一条直线时都当成中间斜率，所以不会重复也不会遗漏。

下面是 AC 代码。

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

#define int long long

const int M = 1e9+7;

int n,ans,r[300005];
double k[300005];

signed main()
{
    cin>>n;
    for(int i=1,a,b,c;i<=n&&cin>>a>>b>>c;i++)
        k[i] = (b!=0 ? -1.0*a/b : 2e17);
    sort(k+1,k+1+n);
    int now=1;
    for(int i=1;i<=n;i++)
    {
        if(i<now) continue;
        while(k[now]==k[i])
            r[i] = now, now++;
    }
    for(int i=1;i<=n;i++)
        if(r[i]>0)
            ans += (i-1)*(n-r[i])%M*(r[i]-i+1)%M, ans %= M;
    cout<<ans<<endl;

    return 0;
}

祝大家 AC 愉快！