10.25模擬 三角形

1. 三角形
(trokuti.cpp/c/pas)
? 【 問題描述 】
? 平面上有N條直線，用方程A i x + B i y +C i
=0表示。這些直線沒有三線共點的。現在
要你計算出用這些直線可以構造出多少三
角形？
【 輸入格式 】
? 第1行：一個整數N(1 ≤ N≤ 300000)。
? 下面N行：每行3個整數：Ai, Bi 和Ci，
表示對應直線方程的系數。不超過10^9.
【 輸出格式 】
一行，一個整數。
input 1
6
0 1 0
-5 3 0
-5 -2 25
0 1 -3
0 1 -2
-4 -5 29
input 2
5
-5 3 0
-5 -3 -30
0 1 0
3 7 35
1 -2 -1
output 1
10
output 2
10
【 數據規模與約定 】
? 對于40%的數據，N ≤1000；
? 對于100%的數據，N≤300000。

/*暴力亂搞 3個點15分*/
#include<cstdio>
#include<iostream>
using namespace std;
struct node
{int a,b,c;
} f[30010];
int n,g[3010][3010],s[30010]={0};
long long ans=0;
int main()
{
//    freopen("trokuti.in","r",stdin);
//    freopen("trokuti.out","w",stdout);scanf("%d",&n);for (int i=1;i<=n;i++)scanf("%d%d%d",&f[i].a,&f[i].b,&f[i].c);for (int i=1;i<=n-1;i++)for (int j=i+1;j<=n;j++)if ((f[i].a*f[j].b-f[i].b*f[j].a)!=0) {s[i]++;g[i][s[i]]=j;}int x,y;for (int i=1;i<n;i++)for (int j=1;j<=s[i];j++){x=g[i][j];y=s[x];for (int k=1;k<=y;k++){int t=g[x][k];if ((f[i].a*f[t].b-f[i].b*f[t].a)!=0 && (f[x].a*f[t].b-f[x].b*f[t].b)!=0)ans++; }}//printf("%I64d",ans);  cout<<ans;
//    fclose(stdin);
//    fclose(stdout);return 0;                                                      
}

/*正解：先計算斜率 再排序3個不同斜率的直線可構成三角形 當有兩條斜率相同 或 三條斜率都相同時不行 所以要排除這兩種可能 運用數論組合排列*/
#include<cstdio>
#include<iostream>
#include<algorithm>
#define N 300010
using namespace std;
double k[N],a[N],b[N],c[N];
long long n,cnt,len[N];
long long C(long long x,long long num)
{if (num==2)return x*(x-1)/2;if (num==3)return x*(x-1)*(x-2)/6;
}
int main()
{//freopen("trokuti.in","r",stdin);//freopen("trokuti.out","w",stdout);cin>>n;for (long long i=1;i<=n;i++){scanf("%lf%lf%lf",&a[i],&b[i],&c[i]);k[i]=-a[i]/b[i];}sort(k+1,k+n+1);len[++cnt]=1;double now=k[1];for (long long i=2;i<=n;i++)if (k[i]!=now){len[++cnt]=1;now=k[i];}else len[cnt]++;long long ans=C(n,3);for (long long i=1;i<=cnt;i++){if (len[i]>=2)ans-=C(len[i],2)*(n-len[i]);if (len[i]>=3)ans-=C(len[i],3);}cout<<ans;//fcolse(stdin);//fclose(stdout);return 0; 
}

?