Algorithm
Vanya got bored and he painted n distinct points on the plane. After that he connected all the points pairwise and saw that as a result many triangles were formed with vertices in the painted points. He asks you to count the number of the formed triangles with the non-zero area.
The first line contains integer n (1 ≤ n ≤ 2000) — the number of the points painted on the plane.
Next n lines contain two integers each xi, yi ( - 100 ≤ xi, yi ≤ 100) — the coordinates of the i-th point. It is guaranteed that no two given points coincide.
In the first line print an integer — the number of triangles with the non-zero area among the painted points.
4
0 0
1 1
2 0
2 2
3
3
0 0
1 1
2 0
1
1
1 1
0
Note to the first sample test. There are 3 triangles formed: (0, 0) - (1, 1) - (2, 0); (0, 0) - (2, 2) - (2, 0); (1, 1) - (2, 2) - (2, 0).
Note to the second sample test. There is 1 triangle formed: (0, 0) - (1, 1) - (2, 0).
Note to the third sample test. A single point doesn't form a single triangle.
Code Examples
#1 Code Example with C++ Programming
Code -
C++ Programming
#include <bits/stdc++.h>
using namespace std;
int const N = 2001;
int n, a[N], b[N], dp[N][N];
map<pair<int, int>, int> mp;
int main() {
scanf("%d", &n);
for(int i = 0; i < n; ++i)
scanf("%d %d", a + i, b + i);
for(int i = 0; i < N; ++i)
for(int j = 0; j <= i; ++j)
if(i == 0 || i == j)
dp[i][j] = 1;
else
dp[i][j] = dp[i - 1][j] + dp[i - 1][j - 1];
int res = dp[n][3];
for(int i = 0; i < n; ++i) {
mp.clear();
for(int j = i + 1, x, y, gcd; j < n; ++j) {
x = a[j] - a[i];
y = b[j] - b[i];
gcd = __gcd(x, y);
x /= gcd;
y /= gcd;
++mp[{x, y}];
}
for(map<pair<int, int>, int>::iterator it = mp.begin(); it != mp.end(); ++it) {
int cur = it->second;
if(cur <= 2)
res -= dp[cur][2];
}
}
printf("%d\n", max(0, res));
return 0;
}Input
0 0
1 1
2 0
2 2
Output
Demonstration
Codeforces Solution-Vanya and Triangles-Solution in C, C++, Java, Python