Description：

给定平面上的一些点，求这些点能组成的所有三角形的面积之和。

$1\leqslant n\leqslant 3000$

Solution：

先把所有点按 $y$ 排序，然后每次统计这个位置和他之后的位置构成的三角形，把他和后面所有点构成的向量找出来，两两相乘求和就是答案，考虑怎么降低复杂度，按极角排序，然后倒序循环，这样它后面的是和它叉积为正的，前面的叉积为负，然后用叉积统计一下即可。

Code：

#include<algorithm>

#include<iostream>

#include<cstdlib>

#include<cstdio>

#include<cmath>

#include<cctype>

#include<cstring>

using namespace std;

int n;

#define MAXN 3001

typedef long double ll;

struct point

{

	ll x,y;

}p[MAXN];

bool cmp_p(point a,point b){return (a.y == b.y ? a.x < b.x : a.y < b.y);}

typedef point vector;

ll operator * (vector a,vector b){return a.x * b.y - a.y * b.x;}

vector s[MAXN];

int tot = 0;

vector operator - (point a,point b){return (vector){a.x - b.x,a.y - b.y};}

vector operator + (vector a,vector b){return (vector){a.x + b.x,a.y + b.y};}

bool cmp_an(vector a,vector b){return (a * b >= 0);}

int main()

{

	scanf("%d",&n);

	for(int i = 1;i <= n;++i)

	{

		scanf("%Lf%Lf",&p[i].x,&p[i].y);

	}

	sort(p + 1,p + 1 + n,cmp_p);

	ll res = 0;

	for(int i = 1;i <= n;++i)

	{

		tot = 0;

		for(int j = i + 1;j <= n;++j)

		{

			s[++tot] = p[j] - p[i];

		}

		sort(s + 1,s + 1 + tot,cmp_an);

		vector sum;sum.x = 0;sum.y = 0;

		for(int j = tot;j >= 1;--j)

		{

			res += s[j] * sum;

			sum = sum + s[j];

		}

	}

	printf("%.1Lf\n",res / 2);

	return 0;

}