cf#308-D-Vanya and Triangles-平面点集中三角形個数-列挙-n^2 lognを求める

http://codeforces.com/contest/552/problem/D
n,n個の点を与えて,構成する面積がゼロでない三角形の個数を求める.
共c(n,3)種、三点共線を除去すればいいですよ
列挙点i,すべての(j>i)の点に対して,一度の傾きを求め,最後に 点iと構成する傾きKの点数がx個あれば、C(x,2)個の共線三角形があるよ. 全部積み重ねると最後にc(n,3)で減算されるのが答えですね
統計の傾きの部分はmapで比較的に便利です
【注意爆int】【double精度の問題に注意】

#include <cstdio>
#include <cmath>
#include <cstring>
#include <string>
#include <algorithm>
#include <queue>
#include <map>
#include <set>
#include <vector>
#include <iostream>
using namespace std;

const double pi=acos(-1.0);
double eps=0.000001; 
__int64 min(__int64 a,__int64 b)
{return a<b?a:b;} 
__int64 max(__int64 a,__int64 b)
{return a>b?a:b;}

 
struct POINT 
{ 
	int x; 
	int y; 
	POINT(double a=0, double b=0) { x=a; y=b;} //constructor 
	double jijiao;
};
POINT p[2005];
__int64 gcd(__int64 a,__int64 b)
{
	if (!b)return a;
	else return gcd(b,a%b);
}
 double get(__int64 i,__int64 j)
 {
	__int64 y=p[i].y-p[j].y;
	__int64 x=p[i].x-p[j].x; 
	if (!x)return 100000;
	__int64 gd=gcd(x,y);
	x/=gd;
	y/=gd;
	 return (y*1.0/x);
 }

 map <double,__int64 >sb;
 map <double,__int64 >::iterator it;;
int main() 
{

	__int64 n;
	scanf("%I64d",&n);
	__int64 i,j; 
	for (i=1;i<=n;i++) 
		scanf("%d%d",&p[i].x,&p[i].y);   
	__int64 ans=0;
	for (i=1;i<=n;i++)
	{
		sb.clear();
		for(j=i+1;j<=n;j++)
		{ 
			 double k=get(i,j);
			sb[k]++;
		}
		for (it=sb.begin();it!=sb.end();it++)
		{ 
			if (it->second>=2)
			ans+= (it->second)*(it->second-1)/2  ;
		}		 
	}
printf("%I64d
",n*(n-1)*(n-2)/6-ans);
	return 0;
}