D. Vanya and Triangles time limit per test 4 seconds memory limit per test 512 megabytes input standard input output standard output
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.
Input
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.
Output
In the first line print an integer — the number of triangles with the non-zero area among the painted points.
Sample test(s) input
4
0 0
1 1
2 0
2 2
output
3
input
3
0 0
1 1
2 0
output
1
input
1
1 1
output
Note
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.
給你二維坐标下的n個點,問一共能構成多少個面積不為0的三角形。
轉載請注明出處:尋找&星空の孩子
題目連結:http://codeforces.com/contest/552/problem/D
#include<cstdio>
#include<cmath>
#include<iostream>
#define PI acos(-1.0)
using namespace std;
struct Point
{
double x,y;
Point(double x=0,double y=0):x(x),y(y){}
};
typedef Point Vector;
Vector operator + (Vector A,Vector B){return Vector(A.x+B.x,A.y+B.y);}
Vector operator - (Point A,Point B){return Vector(A.x-B.x,A.y-B.y);}
Vector operator * (Vector A,double p){return Vector(A.x*p,A.y*p);}
Vector operator / (Vector A,double p){return Vector(A.x/p,A.y/p);}
bool operator < (const Point& a,const Point& b){return a.x<b.x||(a.x==b.x && a.y<b.y);}
const double eps = 1e-10;
int dcmp(double x){if(fabs(x)<eps)return 0;else return x < 0 ? -1 : 1;}
bool operator == (const Point& a,const Point& b){return dcmp(a.x-b.x)==0 && dcmp(a.y-b.y)==0;}
double Dot(Vector A,Vector B){return A.x*B.x+A.y*B.y;}
double length(Vector A){return sqrt(Dot(A,A));}
double Angle(Vector A,Vector B){return acos(Dot(A,B)/length(A)/length(B));}
double Cross(Vector A,Vector B){return A.x*B.y-B.x*A.y;}
double Area2(Point A,Point B,Point C){return Cross(B-A,C-A);}
inline Point read_point(Point &P)
{
scanf("%lf%lf",&P.x,&P.y);
return P;
}
int main()
{
int n;
Point po[2005];
scanf("%d",&n);
for(int i=0;i<n;i++)
read_point(po[i]);
if(n<3){printf("0\n");return 0;}
int cnt=0;
for(int i=0;i<n;i++)
{
for(int j=i+1;j<n;j++)
{
for(int k=j+1;k<n;k++)
{
if(Area2(po[i],po[j],po[k])!=0) cnt++;
}
}
}
printf("%d\n",cnt);
return 0;
}