Triangles

　

triangles

9/100 发布文章

只需要算取三条斜率不相同的直线的方案数即可。

任取3-取2相同再取1-取3相同

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn=3e5+10;
const ll mod=1e9+7;
int n,m;
ll cnt,ans,tot;
struct node
{
 ll a,b,c,cnt;
}t[maxn],tmp[maxn];
void exgcd(ll a,ll b,ll& x,ll& y)
{
    if(!b) 
 { 
  x=1; 
  y=0; 
 }
    else
 { 
  exgcd(b,a%b,y,x); 
  y-=x*(a/b); 
 }
}
inline bool cmp(node a,node b)
{
 return 1.0*a.a/a.b < 1.0*b.a/b.b;
}
int main(){
 scanf("%d",&n);
 for(int i=1;i<=n;i++) 
  scanf("%lld%lld%lld",&t[i].a,&t[i].b,&t[i].c),tmp[i].cnt=1;
 sort(t+1,t+1+n,cmp);
 cnt=1;
 for(int i=2;i<=n;i++)
 {
  if(1.0*t[i].a/t[i].b==1.0*t[i-1].a/t[i-1].b) 
   tmp[cnt].cnt++;
  else 
   tmp[++cnt]=(node){t[i].a,t[i].b,t[i].c,1};
 }
 for(int i=1;i<=cnt;i++)
 {
  tot=((n-tmp[i].cnt)*(n-tmp[i].cnt-1)/2)%mod*tmp[i].cnt%mod;
  ans=(ans+tot)%mod;
 }
 for(int i=1;i<=cnt;i++)
 {
  tot=tmp[i].cnt*(tmp[i].cnt-1)/2%mod;
  ans=((ans-tot*(n-tmp[i].cnt))%mod+mod)%mod;
 }
 exgcd(3ll,mod,tot,cnt);
 tot=(tot%mod+mod)%mod;
 printf("%lld",ans%mod*tot%mod);
 return 0;
}

相关阅读