trokuti 三角形-白红宇

trokuti 三角形

阅读量：5962 次

发布时间：2019-06-19

本文共 2210 字，大约阅读时间需要 7 分钟。

问题描述

平面上有N条直线，用方程Aix + Biy +Ci =0表示。这些直线没有三线共点的。现在要你计算出用这些直线可以构造出多少三角形？

输入格式

第1行：一个整数N(1 ≤ N≤ 300000)。

下面N行：每行3个整数：Ai, Bi 和Ci，表示对应直线方程的系数。不超过10^9。

输出格式

一行，一个整数。

数据规模与约定

对于40%的数据，N ≤1000；

对于100%的数据，N≤300000。

···································································································································································································································································

注意没有三线共点的。

如果没有平行线，我们直接求Cn3就行了。

但是确实有平行线。

那么……

我们只要减去多余的就可以了。

怎样求多余的呢？

多余的是由我们把平行线算到一个三角形中产生的。

对于每一种斜率k，它产生的多余的个数是一个三角形中三条线全是这种斜率，或者有两条是这种斜率。

那么每种斜率产生的多余的个数是Cm3+Cm2*（n-m），m是这种斜率的直线条数。

#include
     
      #include
      
       #include
       
        #include
        
         #include
         
          #include
          #define LL long long#define N 300009using namespace std;int n,cnt;map 
           
             ma;LL num0;//记斜率不存在的线的个数 LL C[N];LL ans,more[N],s[N]; int main(){ scanf("%d",&n); for(int i=1;i<=n;i++) { double a,b,c; scanf("%lf%lf%lf",&a,&b,&c); if(b==0) {num0++;continue;} double k=-a/b; if(ma[k]==0) {ma[k]=++cnt;C[cnt]=1;} else C[ma[k]]++; } if(num0) C[++cnt]=num0; ans=1ll*(n-2)*(n-1)*n/6; for(int i=cnt;i>=1;i--) { LL t=1ll*C[i]*(C[i]-1)*(C[i]-2)/6+1ll*(C[i]-1)*C[i]/2*(n-C[i]); more[i]=t; } for(int i=1;i<=cnt;i++) ans-=more[i]; printf("%lld",ans); return 0;}

还有一种更巧妙地做法

组成三角形的三条直线的斜率肯定是k1 < k2 < k3

我们只要按照枚举k2就可以啦。

加上k1的个数 * k3的个数*k2的个数

#include
     
      #include
      
       #include
       
        #include
        
         #include
         
          #include
          
           #include
           
            #define N 300009#define LL long longusing namespace std;int n,cnt[N],r,s[N];double K[N];LL ans;int main(){ freopen("trokuti.in","r",stdin); freopen("trokuti.out","w",stdout); scanf("%d",&n); for(int i=1;i<=n;i++) { double a,b,c; scanf("%lf%lf%lf",&a,&b,&c); K[i]=-a/b; } sort(K+1,K+n+1); int num=1; for(int i=2;i<=n;i++) { if(K[i]==K[i-1]) num++; else { cnt[++r]=num; num=1; } } cnt[++r]=num; for(int i=1;i<=r;i++) s[i]+=s[i-1]+cnt[i]; for(int i=1;i<=r;i++) { ans+=1ll*s[i-1]*1ll*(s[r]-s[i])*1ll*cnt[i]; } printf("%lld",ans); return 0;}

转载于:https://www.cnblogs.com/dfsac/p/7587807.html

你可能感兴趣的文章