CodeForces - 552D Vanya and Triangles 물

CodeForces - 552D
Vanya and Triangles
Time Limit: 4000MS
 
Memory Limit: 524288KB
 
64bit IO Format: %I64d & %I64u
Submit Status
Description
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 Input
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

0

Hint
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.
Source
Codeforces Round #308 (Div. 2)
//제목:
점 n개 드릴게요. 삼각형 몇 개 만들 수 있냐고요?
//사고방식:
먼저 모든 상황을sum=C(n,3)로 구하고 구성할 수 없는 삼각형의 개수(3점이 한 직선에 있음)C(kk,3)를 찾아내면 상감하면 구하는 것이다.
kk를 구할 때 무거운 공식을 사용합니다: kk=(sqrt(1+8*cnt)+1)/2;모르면 직접 밀어보면 알 수 있다.

#include<stdio.h>
#include<string.h>
#include<math.h>
#include<algorithm>
#include<iostream>
#define ll long long
#define N 2010
using namespace std;
struct zz
{
	double x;
	double y;
}p[N];
bool cmp1(zz a,zz b)
{
	if(a.x==b.x)
		return a.y<b.y;
	return a.x<b.x;
}
struct ss
{
	double k;
	double b;
}pp[N*N];
bool cmp2(ss a,ss b)
{
	if(a.k==b.k)
		return a.b<b.b;
	return a.k<b.k;
}
ll C(int x,int k)
{
	int i,j;
	ll s=1;
	for(i=x,j=1;i>x-k;i--,j++)
		s*=i,s/=j;
	return s;
}
int main()
{
	int n,i,j,k;
	while(scanf("%d",&n)!=EOF)
	{
		for(i=0;i<n;i++)
			scanf("%lf%lf",&p[i].x,&p[i].y);
		sort(p,p+n,cmp1);
		k=0;
		double x,y;
		for(i=0;i<n-1;i++)
		{
			for(j=i+1;j<n;j++)
			{
				x=(p[j].x-p[i].x);y=(p[j].y-p[i].y);
				if(x==0)
				{
					pp[k].k=1000.0;
					pp[k].b=p[j].x;
				}
				else
				{
					pp[k].k=y/x;
					pp[k].b=p[i].y-pp[k].k*p[i].x;
				}
				k++;
			}
		}
		sort(pp,pp+k,cmp2);
		int cnt=1,kk;
		ll num=C(n,3);
		for(i=0;i<k;i++)
		{
			if(fabs(pp[i].k-pp[i+1].k)<=1e-7&&fabs(pp[i].b-pp[i+1].b)<=1e-7)
				cnt++;
			else
			{
//				printf("%d
",cnt);
				kk=(sqrt(1+8*cnt)+1)/2;
				num-=C(kk,3);
				cnt=1;
			}
		}
		printf("%lld
",num);
	}
	return 0;
}