Contest Link: http://www.codechef.com/CDSM2014
Problem Link: http://www.codechef.com/problems/CHEFTR
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