CHEFTR | Editorial

Contest Link: Contest Page | CodeChef

Problem Link: CHEFTR Problem - CodeChef

Author and Editorialist: Prateek Kumar

PREREQUISITES:

Knowledge of Permutations and Combinations

PROBLEM:

You are given n point out of which only k are collinear. Find the number of triangles that can be formed from these n points

EXPLANATION:

The total number of triangles that can be formed are nC3 - kC3. This is equal to n(n-1)(n-2)/6 - k(k-1)(k-2)/6.
From the number of all the 3 point combinations, we have simply subtracted the number of 3 point combinations of k collinear points.


AUTHOR’S SOLUTION:

http://www.codechef.com/viewsolution/5441107

I think an explaination using a diagram will be much easier to undetstand. Please consider this.