共有n个点且有m条共线的三角形计数-yiteyi-C++库

平面上有n个点，其中m个点是共线的。找到点作为顶点形成的三角形的数量？ 例如：

null

Input :  n = 5, m = 4Output : 6Out of five points, four points are collinear, we can make 6 triangles. Wecan choose any 2 points from 4 collinearpoints and use the single point as 3rdpoint. So total count is 4C2 = 6Input :  n = 10, m = 4Output : 116

推荐：请尝试你的方法 {IDE} 首先，在进入解决方案之前。

三角形数= ^N C _3. – ^M C _3. 这个公式是如何工作的？ 考虑上面的第二个例子。有10个点，其中4个是共线的。这十个点中的任意三个将形成一个三角形。因此，形成三角形相当于选择10个点中的任意三个。可以从中的10个点中选择3个点 ^N C _3. 方式。当没有3个点是共线的时候，由10个点组成的三角形的数量= ¹⁰ C _3. ……（一）同样，当没有3个点是共线的时候，由4个点形成的三角形的数量= ^4. C _3. ……..（二）由于这4个点形成的三角形无效，因此需要形成的三角形数= ¹⁰ C _3. – ^4. C _3. = 120 – 4 = 116

C++

                         // CPP program to count number of triangles                       
                         // with n total points, out of which m are                       
                         // collinear.                       
                         #include <bits/stdc++.h>                       
                         using                                     namespace                                     std;                       
           
                         // Returns value of binomial coefficient                       
                         // Code taken from                           https://goo.gl/vhy4jp                                    
                         int                                     nCk(                                     int                                     n,                                     int                                     k)                       
                         {                       
                                                 int                                     C[k+1];                       
                                                 memset                                     (C, 0,                                     sizeof                                     (C));                       
           
                                                 C[0] = 1;                                     // nC0 is 1                       
           
                                                 for                                     (                                     int                                     i = 1; i <= n; i++)                       
                                                 {                       
                                                 // Compute next row of pascal triangle                       
                                                 // using the previous row                       
                                                 for                                     (                                     int                                     j = min(i, k); j > 0; j--)                       
                                                 C[j] = C[j] + C[j-1];                       
                                                 }                       
                                                 return                                     C[k];                       
                         }                       
           
                         /* function to calculate number of triangle                       
                                                 can be formed */                       
                         int                                     counTriangles(                                     int                                     n,                                     int                                     m)                       
                         {                       
                                                 return                                     (nCk(n, 3) - nCk(m, 3));                       
                         }                       
           
                         /* driver function*/                       
                         int                                     main()                       
                         {                       
                                                 int                                     n = 5, m = 4;                       
                                                 cout << counTriangles(n, m);                       
                                                 return                                     0;                       
                         }                       

JAVA

                         //Java program to count number of triangles                       
                         // with n total points, out of which m are                       
                         // collinear.                       
                         import                                     java.io.*;                       
                         import                                     java.util.*;                       
           
                         class                                     GFG {                       
           
                         // Returns value of binomial coefficient                       
                         // Code taken from                           https://goo.gl/vhy4jp                                    
                         static                                     int                                     nCk(                                     int                                     n,                                     int                                     k)                       
                         {                       
                                                 int                                     [] C=                                     new                                     int                                     [k+                                     1                                     ];                       
                                                 for                                     (                                     int                                     i=                                     0                                     ;i<=k;i++)                       
                                                 C[i]=                                     0                                     ;                       
                                   
                                                 C[                                     0                                     ] =                                     1                                     ;                                     // nC0 is 1                       
           
                                                 for                                     (                                     int                                     i =                                     1                                     ; i <= n; i++)                       
                                                 {                       
                                                 // Compute next row of pascal triangle                       
                                                 // using the previous row                       
                                                 for                                     (                                     int                                     j = Math.min(i, k); j >                                     0                                     ; j--)                       
                                                 C[j] = C[j] + C[j-                                     1                                     ];                       
                                                 }                       
                                                 return                                     C[k];                       
                         }                       
           
                         /* function to calculate number of triangle                       
                         can be formed */                       
                         static                                     int                                     counTriangles(                                     int                                     n,                                     int                                     m)                       
                         {                       
                                                 return                                     (nCk(n,                                     3                                     ) - nCk(m,                                     3                                     ));                       
                         }                       
           
                                                 public                                     static                                     void                                     main (String[] args) {                       
                                                 int                                     n =                                     5                                     , m =                                     4                                     ;                       
                                                 System.out.println(counTriangles(n, m));                       
           
                                                 }                       
                         }                       
           
                         //This code is contributed by Gitanjali.                       

Python3

                         # python program to count number of triangles                       
                         # with n total points, out of which m are                       
                         # collinear.                       
                         import                                     math                       
                                   
                         # Returns value of binomial coefficient                       
                         # Code taken from                           https://goo.gl                          / vhy4jp                       
                         def                                     nCk(n, k):                       
                                                 C                                     =                                     [                                     0                                     for                                     i                                     in                                     range                                     (                                     0                                     , k                                     +                                     2                                     )]                       
                                   
                                                 C[                                     0                                     ]                                     =                                     1                                     ;                                     # nC0 is 1                       
                                                 for                                     i                                     in                                     range                                     (                                     0                                     , n                                     +                                     1                                     ):                       
                                   
                                                 # Compute next row of pascal triangle                       
                                                 # using the previous row                       
                                                 for                                     j                                     in                                     range                                     (                                     min                                     (i, k),                                     0                                     ,                                     -                                     1                                     ):                       
                                                 C[j]                                     =                                     C[j]                                     +                                     C[j                                     -                                     1                                     ]                       
                                   
                                                 return                                     C[k]                       
                                   
                         # function to calculate number of triangle                       
                         # can be formed                       
                         def                                     counTriangles(n, m):                       
                                                 return                                     (nCk(n,                                     3                                     )                                     -                                     nCk(m,                                     3                                     ))                       
                                   
                         # driver code                       
                         n                                     =                                     5                       
                         m                                     =                                     4                       
                         print                                     (counTriangles(n, m))                       
                                   
                         # This code is contributed by Gitanjali                       

C#

                         //C# program to count number of triangles                       
                         // with n total points, out of which m are                       
                         // collinear.                       
                         using                                     System;                       
           
                         class                                     GFG {                       
           
                                                 // Returns value of binomial coefficient                       
                                                 // Code taken from                           https://goo.gl/vhy4jp                                    
                                                 static                                     int                                     nCk(                                     int                                     n,                                     int                                     k)                       
                                                 {                       
                                                 int                                     [] C=                                     new                                     int                                     [k+1];                       
                                                 for                                     (                                     int                                     i = 0; i <= k; i++)                       
                                                 C[i] = 0;                       
                                   
                                                 // nC0 is 1                       
                                                 C[0] = 1;                       
                                   
                                                 for                                     (                                     int                                     i = 1; i <= n; i++)                       
                                                 {                       
                                                 // Compute next row of pascal triangle                       
                                                 // using the previous row                       
                                                 for                                     (                                     int                                     j = Math.Min(i, k); j > 0; j--)                       
                                                 C[j] = C[j] + C[j - 1];                       
                                                 }                       
                                                 return                                     C[k];                       
                                                 }                       
                                   
                                                 /* function to calculate number of triangle                       
                                                 can be formed */                       
                                                 static                                     int                                     counTriangles(                                     int                                     n,                                     int                                     m)                       
                                                 {                       
                                                 return                                     (nCk(n, 3) - nCk(m, 3));                       
                                                 }                       
                                   
                                                 // Driver code                       
                                                 public                                     static                                     void                                     Main ()                       
                                                 {                       
                                                 int                                     n = 5, m = 4;                       
                                                 Console.WriteLine(counTriangles(n, m));                       
           
                                                 }                       
                         }                       
           
                         // This code is contributed by vt_m.                       

PHP

                         <?php                       
                         // PHP program to count number                       
                         // of triangles with n total                       
                         // points, out of which m are collinear.                       
           
                         // Returns value of binomial coefficient                       
                         // Code taken from                           https://goo.gl/vhy4jp                                    
                         function                                     nCk(                                     $n                                     ,                                     $k                                     )                       
                         {                       
                                                 for                                     (                                     $i                                     = 0;                                     $i                                     <=                                     $k                                     ;                                     $i                                     ++)                       
                                                 $C                                     [                                     $i                                     ] = 0;                       
           
                                                 $C                                     [0] = 1;                                     // nC0 is 1                       
           
                                                 for                                     (                                     $i                                     = 1;                                     $i                                     <=                                     $n                                     ;                                     $i                                     ++)                       
                                                 {                       
                                                 // Compute next row of pascal                       
                                                 // triangle using the previous row                       
                                                 for                                     (                                     $j                                     = min(                                     $i                                     ,                                     $k                                     );                                     $j                                     > 0;                                     $j                                     --)                       
                                                 $C                                     [                                     $j                                     ] =                                     $C                                     [                                     $j                                     ] +                                     $C                                     [                                     $j                                     - 1];                       
                                                 }                       
                                                 return                                     $C                                     [                                     $k                                     ];                       
                         }                       
           
                         /* function to calculate number                       
                         of triangles that can be formed */                       
                         function                                     counTriangles(                                     $n                                     ,                                     $m                                     )                       
                         {                       
                                                 return                                     (nCk(                                     $n                                     , 3) - nCk(                                     $m                                     , 3));                       
                         }                       
           
                         // Driver Code                       
                         $n                                     = 5;                       
                         $m                                     = 4;                       
                         echo                                     counTriangles(                                     $n                                     ,                                     $m                                     );                       
                         return                                     0;                       
           
                         // This code is contributed by ChitraNayal                       
                         ?>                       

Javascript

                         <script>                       
                                                 // Javascript program to count number of triangles                       
                                                 // with n total points, out of which m are                       
                                                 // collinear.                       
                                   
                                                 // Returns value of binomial coefficient                       
                                                 // Code taken from                           https://goo.gl/vhy4jp                                    
                                                 function                                     nCk(n, k)                       
                                                 {                       
                                                 let C =                                     new                                     Array(k+1);                       
                                                 C.fill(0);                       
           
                                                 C[0] = 1;                                     // nC0 is 1                       
           
                                                 for                                     (let i = 1; i <= n; i++)                       
                                                 {                       
                                                 // Compute next row of pascal triangle                       
                                                 // using the previous row                       
                                                 for                                     (let j = Math.min(i, k); j > 0; j--)                       
                                                 C[j] = C[j] + C[j-1];                       
                                                 }                       
                                                 return                                     C[k];                       
                                                 }                       
           
                                                 /* function to calculate number of triangle                       
                                                 can be formed */                       
                                                 function                                     counTriangles(n, m)                       
                                                 {                       
                                                 return                                     (nCk(n, 3) - nCk(m, 3));                       
                                                 }                       
                                   
                                                 let n = 5, m = 4;                       
                                                 document.write(counTriangles(n, m));                       
                                   
                                                 // This code is contributed by divyesh072019.                       
                         </script>                       

输出：

文章版权归作者所有，未经允许请勿转载。

THE END

技术文章