自动搬运

查看原文

来自洛谷，原作者为

	kouylan 这人真的菜 | 已AFO

搬运于2025-08-24 22:32:06，当前版本为作者最后更新于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 愉快！