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; }

?

轉載于:https://www.cnblogs.com/xiaoqi7/p/5997868.html

總結

以上是生活随笔為你收集整理的10.25模拟 三角形的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。