Given N dots that are evenly spaced on the circumference of a circle, how many combinations of three dots can we pick from those N dots that do not form a equilateral triangle?

Sample Input:

N =15

Sample Output:

450

Intuition

• To choose 3 out of 15 is typical combination question. So the answer for that is 15! / (15-3)! 3!
• Next step is to figure out how many equilateral triangles will be there for evenly spaced 15 dots.
• With 15 dots, the number of equilateral triangles are 15 / 3 = 5
• So the final result is 15! / (15-3)! 3! – 5 = 455 – 5 = 450

The image above shows the 5 equilateral triangles with 15 evenly points.

数据结构和算法：初级练习题 #61 阶乘和组合（二）

给定圆周上均匀分布的 N 个点，选择三个点的组合形成的三角形里面，有多少个非等边三角形？

输入样例：

N = 15

输出样例：

450

从15个圆周上均匀分布的点选择三点组成的三角形中，有450个非等边三角形。

算法思路

• 从 15 个点中选择三个点的组合数是： 15! / (15-3)! 3! = 455
• 15 个点可以组成的等边三角形是 15 / 3 = 5
• 最后结果是： 455 – 5 = 450
• 上面的图形展示了15个点可以形成的五个等边三角形。

Python Solution